
\chapter{The logic of types. II. Curried functions\label{chap:Higher-order-functions} }

\section{Functions that return functions}

\subsection{Motivation and first examples}

\global\long\def\gunderline#1{\mathunderline{greenunder}{#1}}%
\global\long\def\bef{\forwardcompose}%
Consider the task of preparing a logger function that prints messages
with a configurable prefix. 

A simple logger function can be a value of type \lstinline!String => Unit!,
such as
\begin{lstlisting}
val logger: String => Unit = { message => println(s"INFO: $message") }

scala> logger("hello world")
INFO: hello world
\end{lstlisting}
This function prints any given message with the logging prefix \lstinline!"INFO"!. 

The standard library function \lstinline!println(...)! always returns
a \lstinline!Unit! value after printing its arguments. As we already
know, there is only a single value of type \lstinline!Unit!, and
that value is denoted by \lstinline!()!. To see that \lstinline!println!
returns \lstinline!Unit!, run this code:
\begin{lstlisting}
scala> val x = println(123)
123
x: Unit = ()
\end{lstlisting}

The task is to make the logging prefix configurable. A simple solution
is to implement a function \lstinline!logWith! that takes a prefix
as an argument and returns a new logger containing that prefix. Note
that the function \lstinline!logWith! returns a new \emph{function},
i.e., a new value of type \lstinline!String => Unit!:
\begin{lstlisting}
def logWith(prefix: String): (String => Unit) = {
    message => println(s"$prefix: $message")
}
\end{lstlisting}
The body of \lstinline!logWith! consists of a nameless function \lstinline!message => println(...)!,
which is a value of type \lstinline!String => Unit!. This value will
be returned when we evaluate \lstinline!logWith("...")!.

We can now use \lstinline!logWith! to create some logger functions:
\begin{lstlisting}
scala> val info = logWith("INFO")
info: String => Unit = <function1>

scala> val warn = logWith("WARN")
warn: String => Unit = <function1>
\end{lstlisting}
The created loggers are then usable as ordinary functions:
\begin{lstlisting}
scala> info("hello")
INFO: hello

scala> warn("goodbye")
WARN: goodbye
\end{lstlisting}
The values \lstinline!info! and \lstinline!warn! can be used by
any code that needs a logging function.

It is important that the prefix is \textsf{``}baked into\textsf{''} functions created
by \lstinline!logWith!. A logger such as \lstinline!warn! will always
print messages with the prefix \lstinline!"WARN"!, and the prefix
cannot be changed any more. This is because the value \lstinline!prefix!
is treated as a local constant within the body of the nameless function
computed and returned by \lstinline!logWith!. For instance, the body
of the function \lstinline!warn! is equivalent to
\begin{lstlisting}
{ val prefix = "WARN"; (message => s"$prefix: $message") }
\end{lstlisting}
Whenever a new function is created using \lstinline!logWith(prefix)!,
the (immutable) value of \lstinline!prefix! is stored within the
body of the newly created function. This is a general feature of nameless
functions: the function\textsf{'}s body keeps copies of all the outer-scope
values it uses. One sometimes says that the function\textsf{'}s body \textsf{``}closes
over\textsf{''} those values; for this reason, nameless functions are also
called \textsf{``}\textbf{\index{closure}closures}\textsf{''}. It would be clearer
to say that nameless functions \textsf{``}capture\textsf{''} values from outer scopes.

As another example of the capture of values, consider this code:
\begin{lstlisting}
val f: (Int => Int) = {
  val p = 10
  val q = 20
  x => p + q * x
}
\end{lstlisting}
The body of the function \lstinline!f! is equivalent to \lstinline!{ x => 10 + 20 * x }!
because the values \lstinline!p = 10! and \lstinline!q = 20! were
captured.

The parentheses around a function\textsf{'}s type, such as \lstinline!(Int => Int)!,
are optional in Scala. 

\subsection{Curried and uncurried functions}

Reasoning mathematically about the code
\begin{lstlisting}
val info = logWith("INFO")
info("hello")
\end{lstlisting}
we would expect that \lstinline!info! is \emph{the same value} as
\lstinline!logWith("INFO")!, and so the code \lstinline!info("hello")!
should have the same effect as the code \lstinline!logWith("INFO")("hello")!.
This is indeed so:
\begin{lstlisting}
scala> logWith("INFO")("hello")
INFO: hello
\end{lstlisting}
The syntax \lstinline!logWith("INFO")("hello")! looks like the function
\lstinline!logWith! applied to \emph{two} arguments. Yet, \lstinline!logWith!
was defined as a function with a single argument of type \lstinline!String!.
This is not a contradiction because \lstinline!logWith("INFO")! returns
a function that accepts an additional argument. So, expressions \lstinline!logWith("INFO")!
and \lstinline!logWith("INFO")("hello")! are both valid. In this
sense, we are allowed to apply \lstinline!logWith! to one argument
at a time.

A function that can be applied to arguments in this way is called
a \index{curried function}\textbf{curried} function. 

While a curried function can be applied to one argument at a time,
an \textbf{uncurried}\index{uncurried function} function must be
applied to all arguments at once, e.g.
\begin{lstlisting}
def prefixLog(prefix: String, message: String): Unit = println(s"$prefix: $message")
\end{lstlisting}

The type of the curried function \lstinline!logWith! is \lstinline!String => (String => Unit)!.
By Scala\textsf{'}s syntax conventions, the function arrow (\lstinline!=>!)
groups to the \emph{right}. So the parentheses in the type expression
\lstinline!String => (String => Unit)! are not needed; the function\textsf{'}s
type can be written as \lstinline!String => String => Unit!.

The type \lstinline!String => String => Unit! is different from \lstinline!(String => String) => Unit!,
which is the type of a function returning \lstinline!Unit! and having
a function of type \lstinline!String => String! as its argument.
When an argument\textsf{'}s type is a function type, e.g., \lstinline!String => String!,
it must be enclosed in parentheses.

In general, a curried function takes an argument and returns another
function that again takes an argument and returns another function,
and so on, until finally a non-function type is returned. So, the
type signature of a curried function generally looks like \lstinline!A => B => C => ... => R => S!,
where \lstinline!A!, \lstinline!B!, ..., \lstinline!R! are the
\textbf{curried arguments}\index{curried arguments} and \lstinline!S!
is the \textsf{``}final\textsf{''} result type.

For example, in the type expression \lstinline!A => B => C => D!
the types \lstinline!A!, \lstinline!B!, \lstinline!C! are the types
of curried arguments, and \lstinline!D! is the final result type.
It takes time to get used to reading this kind of syntax.

In Scala, functions defined with multiple argument groups (enclosed
in multiple pairs of parentheses) are curried functions. We have seen
examples of curried functions before:
\begin{lstlisting}
def map[A, B](xs: Seq[A])(f: A => B): Seq[B]
def fmap[A, B](f: A => B)(xs: Option[A]): Option[B]
def foldLeft[A, R](xs: Seq[A])(init: R)(update: (R, A) => R): R
\end{lstlisting}
The type signatures of these functions can be also written equivalently
as
\begin{lstlisting}
def map[A, B]: Seq[A] => (A => B) => Seq[B]
def fmap[A, B]: (A => B) => Option[A] => Option[B]
def foldLeft[A, R]: Seq[A] => R => ((R, A) => R) => R
\end{lstlisting}
Curried arguments of a \emph{function type}, such as \lstinline!(A => B)!,
need parentheses.

To summarize, a curried function such as \lstinline!logWith! can
be defined in three equivalent ways in Scala:
\begin{lstlisting}[numbers=left]
def logWith1(prefix: String)(message: String): Unit = println(s"$prefix: $message")
def logWith2(prefix: String): String => Unit = { message => println(s"$prefix: $message") }
def logWith3: String => String => Unit = { prefix => message => println(s"$prefix: $message") }
\end{lstlisting}
We will sometimes enclose nameless functions in parentheses or curly
braces to improves clarity. 

Line 3 above shows that the arrow symbols \lstinline!=>! group to
the right within the \emph{code} of nameless functions: \lstinline!x => y => expr!
means \lstinline!{x => {y => expr}}!, a nameless function taking
an argument \lstinline!x! and returning a nameless function that
takes an argument \lstinline!y! and returns an expression \lstinline!expr!.
This syntax convention is helpful since the code \lstinline!x => y => z!
visually corresponds to the curried function\textsf{'}s type signature \lstinline!A => B => C!,
which uses the same syntax convention. Also, the syntax \lstinline!(x => y) => z!
could not possibly work for a nameless function because it would be
an argument match with the pattern \lstinline!x => y!. If we matched
a function such as \lstinline!{ t => t + 20 }! against the pattern
\lstinline!x => y! by setting \lstinline!x = t! and \lstinline!y = t + 20!,
we would have no value for the bound variable \lstinline!t!. (What
would be the integer value of \lstinline!y!?) So \lstinline!x => (y => z)!
is the only sensible way of inserting parentheses into \lstinline!x => y => z!.

Although the code \lstinline!(x => y) => z! is invalid, a type expression
\lstinline!(A => B) => C! is valid. A nameless function of type \lstinline!(A => B) => C!
is written as \lstinline!f => expr! where \lstinline!f: A => B!
is its argument and \lstinline!expr! its body. 

\subsection{Equivalence of curried and uncurried functions}

We defined the curried function \lstinline!logWith! in order to be
able to create logger functions such as \lstinline!info! and \lstinline!warn!.
However, some curried functions, such as \lstinline!foldLeft!, are
almost always applied to all possible arguments. A curried function
applied to all its possible arguments is equivalent to an uncurried
function that takes all those arguments at once. Let us look at this
equivalence in more detail.

Consider a curried function with type signature \lstinline!Int => Int => Int!.
This function takes an integer and returns an (uncurried) function
taking an integer and returning an integer. An example of such a curried
function is
\begin{lstlisting}
def f1(x: Int): Int => Int = { y => x - y }
\end{lstlisting}

The function takes an integer \lstinline!x! and returns the expression
\lstinline!y => x - y!, which is a function of type \lstinline!Int => Int!.
The code of \lstinline!f1! can be written equivalently as
\begin{lstlisting}
val f1: Int => Int => Int = { x => y => x - y }
\end{lstlisting}

Let us compare the function \lstinline!f1! with a function that takes
its two arguments at once, e.g.
\begin{lstlisting}
def f2(x: Int, y: Int): Int = x - y
\end{lstlisting}
The function \lstinline!f2! has type signature \lstinline!(Int, Int) => Int!.

The syntax for using the functions \lstinline!f1! and \lstinline!f2!
is different:
\begin{lstlisting}
scala> f1(20)(4)
res0: Int = 16

scala> f2(20, 4)
res1: Int = 16
\end{lstlisting}
The main difference between the usage of \lstinline!f1! and \lstinline!f2!
is that \lstinline!f2! must be applied at once to both arguments,
while \lstinline!f1! applied to just the first argument, \lstinline!20!.
The result of evaluating \lstinline!f1(20)! is a function that can
be later applied to another argument:
\begin{lstlisting}
scala> val r1 = f1(20)
r1: Int => Int = <function1> 

scala> r1(4)
res2: Int = 16
\end{lstlisting}

Applying a curried function to some but not all possible arguments
is called a \textbf{\index{partial application}partial application}.
Applying a curried function to all possible arguments is called a
\index{saturated application}\textbf{saturated} application.

If we need to partially apply an \emph{uncurried} function, we can
use the underscore ($\_$) symbol:

\begin{wrapfigure}{l}{0.45\columnwidth}%
\vspace{-0.9\baselineskip}
\begin{lstlisting}[numbers=left]
scala> val r2: Int => Int = f2(20, _)
r2: Int => Int = <function1>

scala> r2(4)
res3: Int = 16
\end{lstlisting}
\vspace{-0.95\baselineskip}
\end{wrapfigure}%

\noindent (The type annotation \lstinline!Int => Int! is required
in line 1.) This code creates a function \lstinline!r2! by partially
applying \lstinline!f2! to the first argument but not to the second.
Other than that, \lstinline!r2! is the same function as \lstinline!r1!
defined above; i.e., \lstinline!r2! returns the same values for the
same arguments as \lstinline!r1!. A more straightforward syntax for
a partial application is
\begin{lstlisting}
scala> val r3: Int => Int = { x => f2(20, x) }    // Same as r2 above.
r3: Int => Int = <function1>

scala> r3(4)
res4: Int = 16
\end{lstlisting}

We can see that a curried function, such as \lstinline!f1!, is better
adapted for partial application than \lstinline!f2!, because the
syntax is shorter. However, the types of functions \lstinline!f1!
and \lstinline!f2! are\textbf{ equivalent}\index{type equivalence}:
for any \lstinline!f1! we can reconstruct \lstinline!f2! and vice
versa, without loss of information:
\begin{lstlisting}
def f2new(x: Int, y: Int): Int = f1(x)(y)             // f2new is equal to f2
def f1new: Int => Int => Int = { x => y => f2(x, y) } // f1new is equal to f1
\end{lstlisting}
It is clear that the function \lstinline!f1new! computes the same
results as \lstinline!f1!, and that the function \lstinline!f2new!
computes the same results as \lstinline!f2!. The equivalence of the
functions \lstinline!f1! and \lstinline!f2! is not \emph{equality}
 \textemdash{} these functions are \emph{different}; but each of them
can be reconstructed from the other. 

More generally, a curried function has a type signature of the form
\lstinline!A => B => C => ... => R => S!, where \lstinline!A!, \lstinline!B!,
\lstinline!C!, ..., \lstinline!S! are some types. A function with
this type signature is equivalent to an uncurried\index{uncurried function}
function with type signature \lstinline!(A,B,C,...,R) => S!. The
uncurried function takes all arguments at once, while the curried
function takes one argument at a time. Other than that, these two
functions compute the same results given the same arguments.

We have seen how a curried function can be converted to an equivalent
uncurried one, and vice versa. The Scala library defines the methods
\lstinline!curried! and \lstinline!uncurried! that convert between
these forms of functions. To convert between \lstinline!f2! and \lstinline!f1!:

\begin{wrapfigure}{l}{0.42\columnwidth}%
\vspace{-0.9\baselineskip}
\begin{lstlisting}
scala> val f1c = (f2 _).curried
f1c: Int => (Int => Int) = <function1>

scala> val f2u = Function.uncurried(f1c)
f2u: (Int, Int) => Int = <function2> 
\end{lstlisting}
\vspace{-0.95\baselineskip}
\end{wrapfigure}%

\noindent The syntax \lstinline!(f2 _)! is needed in Scala to convert
methods to function values. Recall that Scala has two ways of defining
a function: one as a method\index{Scala method} (defined using \lstinline!def!),
another as a function value\index{function value} (defined using
\lstinline!val!). The extra underscore will become unnecessary in
Scala 3.

The methods \lstinline!curried! and \lstinline!uncurried! are quick
to implement, as we will show in Section~\ref{subsec:Examples-of-fully-parametric}.
These functions are called the \textbf{currying}\index{currying}
and \textbf{uncurrying}\index{uncurrying} transformations.

\section{Fully parametric functions\label{sec:Fully-parametric-functions}}

We have seen that some functions are declared with type parameters,
which are set only when the function is applied to specific arguments.
Examples of such functions are \lstinline!map! and \lstinline!filter!,
written as
\begin{lstlisting}
def map[A, B](xs: Seq[A])(f: A => B): Seq[B]
def filter[A](xs: Seq[A])(p: A => Boolean): Seq[A]
\end{lstlisting}
Such functions can be applied to arguments of different types without
changing the function\textsf{'}s code. It is clearly better to implement a
single function with type parameters instead of writing several functions
with repeated code but working with different types.

When we apply the function \lstinline!map! as \lstinline!map(xs)(f)!
to a specific value \lstinline!xs! of type, e.g., \lstinline!Seq[Int]!,
and a specific function \lstinline!f! of type, say, \lstinline!Int => String!,
the Scala compiler will automatically set the type parameters \lstinline!A = Int!
and \lstinline!B = String! in the code of \lstinline!map!. We may
also set type parameters explicitly and write, for example, \lstinline!map[Int, String](xs)(f)!.
This syntax shows a certain similarity between type parameters such
as \lstinline!Int!, \lstinline!String! and \textsf{``}value parameters\textsf{''}
(arguments) \lstinline!xs! and \lstinline!f!. Setting type parameters,
e.g., \lstinline!map[Int, String]!, means substituting \lstinline!A = Int!,
\lstinline!B = String! into the type signature of the function, similarly
to how setting value parameters means substituting specific values
into the function body.

In the functions \lstinline!map! and \lstinline!filter! as just
shown, some types are parameters while others are specific types,
such as \lstinline!Seq! and \lstinline!Boolean!. It is sometimes
possible to replace \emph{all} specific types in the type signature
of a function by type parameters. The result is a \textsf{``}fully parametric\textsf{''}
function.

We call a function \textbf{fully parametric}\index{fully parametric!function}
if its arguments have types described by type parameters, and the
code of the function treats all types as type parameters. In other
words, fully parametric functions do not use any values of specific
types, such as \lstinline!Int! or \lstinline!String!, in their code.
A fully parametric function does not use any information about its
argument types, other than assuming that those types correctly match
the type signature.

What kind of functions are fully parametric? To build up intuition,
let us compare the following two functions that have the same type
signature:
\begin{lstlisting}
def cos_sin(p: (Double, Double)): (Double, Double) = p match {
  case (x, y) =>
    val r = math.sqrt(x * x + y * y)
    (x / r, y / r) // Return cos and sin of the angle.
}

def swap(p: (Double, Double)): (Double, Double) = p match {
  case (x, y) => (y, x)
}
\end{lstlisting}
We can introduce type parameters into the type signature of \lstinline!swap!
to make it fully parametric:

\begin{wrapfigure}{l}{0.5\columnwidth}%
\vspace{-0.55\baselineskip}
\begin{lstlisting}
def swap[A, B](p: (A, B)): (B, A) = p match {
  case (x, y) => (y, x)
}
\end{lstlisting}
\vspace{-0.95\baselineskip}
\end{wrapfigure}%

\noindent Converting \lstinline!swap! into a fully parametric function
is possible because the operation of swapping two parts of a tuple
\lstinline!(A, B)! works in the same way for all types \lstinline!A!,
\lstinline!B!. No changes were made in the body of the function.
The specialized version of \lstinline!swap! working on \lstinline!(Double, Double)!
can be obtained from the fully parametric version of \lstinline!swap!
if we set the type parameters as \lstinline!A = Double!, \lstinline!B = Double!.

In contrast, the function \lstinline!cos_sin! performs a computation
that is specific to the type \lstinline!Double! and cannot be generalized
to an arbitrary type parameter \lstinline!A! instead of \lstinline!Double!.
So, \lstinline!cos_sin! cannot be generalized to a fully parametric
function.

Typically, a fully parametric function has all its arguments typed
with type parameters or with some combinations of type parameters,
i.e., type expressions such as \lstinline!(A, B)! or \lstinline!X => Either[X, Y]!.

The \lstinline!swap! operation for pairs is already defined in the
Scala library:
\begin{lstlisting}
scala> (1, "abc").swap
res0: (String, Int) = (abc,1)
\end{lstlisting}
If needed, other swapping functions can be implemented for tuples
with more elements, e.g.
\begin{lstlisting}
def swap12[A,B,C]: ((A, B, C)) => (B, A, C) = { case (x, y, z) => (y, x, z) }
\end{lstlisting}
The Scala syntax requires the double parentheses around tuple types\index{tuples!as function arguments}
of arguments but not around the tuple type of a function\textsf{'}s result.
So, the function \lstinline!cos_sin! may be written as a value of
type
\begin{lstlisting}
val cos_sin: ((Double, Double)) => (Double, Double) = ...
\end{lstlisting}


\subsection{Examples. Function composition\label{subsec:Examples-of-fully-parametric}}

Further examples of fully parametric functions are the identity function,
the constant function, the function composition methods, and the currying
/ uncurrying transformations. 

The \index{identity function}identity function (available in the
Scala library as \lstinline!identity[T]!) is
\begin{lstlisting}
def id[T]: T => T = (t => t)
\end{lstlisting}
The constant function\index{constant function} (available in the
Scala library as \lstinline!Function.const[C, X]!) takes an argument
\lstinline!c:C! and returns a new function that always returns \lstinline!c!:
\begin{lstlisting}
def const[C, X](c: C): X => C = (_ => c)
\end{lstlisting}
The syntax \lstinline!_ => c! is used to emphasize that the function
ignores its argument.

\paragraph{Function composition}

\index{function composition}Consider two functions \lstinline!f: Int => Double!
and \lstinline!g: Double => String!. We can apply \lstinline!f!
to an integer argument \lstinline!x:Int! and get a result \lstinline!f(x)!
of type \lstinline!Double!. Applying \lstinline!g! to that result
gives a \lstinline!String! value \lstinline!g(f(x))!. The transformation
from the original integer \lstinline!x:Int! to the final \lstinline!String!
value \lstinline!g(f(x))! can be viewed as a new function of type
\lstinline!Int => String!. That new function is called the \textbf{forward
composition}\index{forward composition} of the two functions \lstinline!f!
and \lstinline!g!. In Scala, this operation is written as \lstinline!f andThen g!:
\begin{lstlisting}
val f: Int => Double = (x => 5.67 + x)
val g: Double => String = (x => f"Result x = $x%3.2f")

scala> val h = f andThen g       // h(x) is defined as g(f(x)).
h: Int => String = <function1>

scala> h(40)
res36: String = Result x = 45.67
\end{lstlisting}
The Scala compiler derives the type of \lstinline!h! automatically
as \lstinline!Int => String!.

The forward composition is denoted by $\bef$ (pronounced \textsf{``}before\textsf{''})
and can be defined as
\begin{equation}
f\bef g\triangleq x\rightarrow g(f(x))\quad.\label{eq:def-of-forward-composition}
\end{equation}
The symbol $\triangleq$ means \textsf{``}is defined as\textsf{''}.

We could implement the operation of forward composition as a fully
parametric function,
\begin{lstlisting}
def andThen[X, Y, Z](f: X => Y)(g: Y => Z): X => Z = { x => g(f(x)) }
\end{lstlisting}
This type signature requires the types of the function arguments to
match in a certain way, or else the composition is undefined (and
the code would produce a type error).

The method \lstinline!andThen! is an example of a function that \emph{both}
returns a new function \emph{and} takes other functions as arguments.

The \textbf{backward composition}\index{backward composition} of
two functions $f$ and $g$ works in the opposite order: first $g$
is applied and then $f$. Using the symbol $\circ$ (pronounced \textsf{``}after\textsf{''})
for this operation, we can write
\begin{equation}
f\circ g\triangleq x\rightarrow f(g(x))\quad.\label{eq:def-of-backward-composition}
\end{equation}
In Scala, the backward composition is called \lstinline!compose!
and used as \lstinline!f compose g!. This method may be implemented
as a fully parametric function
\begin{lstlisting}
def compose[X, Y, Z](f: Y => X)(g: Z => Y): Z => X = { z => f(g(z)) }
\end{lstlisting}

We have already seen the methods \lstinline!curried! and \lstinline!uncurried!
defined by the Scala library. As an illustration, here is the code
for the \textbf{uncurrying}\index{uncurrying} transformation (converting
curried functions to uncurried):
\begin{lstlisting}
def uncurry[A, B, R](f: A => B => R): ((A, B)) => R = { case (a, b) => f(a)(b) }
\end{lstlisting}

We conclude from these examples that fully parametric functions perform
operations so general that they work in the same way for all types.
Some arguments of fully parametric functions may have complicated
types such as \lstinline!A => B => R!, which are type expressions
built up from type parameters. But fully parametric functions do not
use values of specific types such as \lstinline!Int! or \lstinline!String!.

Functions with type parameters are sometimes called \textsf{``}generic\index{generic functions}\textsf{''}.
This book uses the term \textsf{``}\index{fully parametric!function}\textbf{fully
parametric}\textsf{''} to designate a certain restricted kind of generic functions.

\subsection{Laws of function composition\label{subsec:Laws-of-function-composition}}

The operations of function composition, introduced in Section~\ref{subsec:Examples-of-fully-parametric},
have three important properties or \textsf{``}laws\textsf{''} that follow directly
from the definitions. These laws are:
\begin{itemize}
\item The two \textbf{identity laws}\index{identity laws!of function composition}:
the composition of any function $f$ with the identity function will
give again the function $f$.
\item The \textbf{associativity law}\index{associativity law!of function composition}:
the consecutive composition of three functions $f$, $g$, $h$ does
not depend on the order in which the pairs are composed.
\end{itemize}
These laws hold equally for the forward and the backward composition,
since those are just syntactic variants of the same operation. Let
us write these laws rigorously as equations and prove them.

\paragraph{Proofs with forward composition}

The composition of the identity function with an arbitrary function
$f$ can be $\text{id}\bef f$ with the identity function to the left
of $f$, or $f\bef\text{id}$ with the identity function to the right
of $f$. In both cases, the result must be equal to the function $f$.
The resulting two laws are
\begin{align*}
{\color{greenunder}\text{left identity law of composition}:}\quad & \text{id}\bef f=f\quad,\\
{\color{greenunder}\text{right identity law of composition}:}\quad & f\bef\text{id}=f\quad.
\end{align*}
To show that these laws always hold, we need to show that both sides
of the laws, which are functions, give the same result when applied
to an arbitrary value $x$. Let us first clarify how the type parameters
must be set for the laws to have consistently matching types.

The laws must hold for an arbitrary function $f$. So we may assume
that $f$ has the type signature $A\rightarrow B$, where $A$ and
$B$ are arbitrary type parameters. Consider the left identity law.
The function $(\text{id}\bef f)$ is, by definition~(\ref{eq:def-of-forward-composition}),
a function that takes an argument $x$, applies $\text{id}$ to that
$x$, and then applies $f$ to the result: 
\[
\text{id}\bef f=\left(x\rightarrow f(\text{id}\,(x))\right)\quad.
\]
If $f$ has type $A\rightarrow B$, its argument must be of type $A$,
or else the types will not match. Therefore, the identity function
must have type $A\rightarrow A$, and the argument $x$ must have
type $A$. With these choices of the type parameters, the function
$\left(x\rightarrow f(\text{id}(x))\right)$ will have type $A\rightarrow B$,
as it must since the right-hand side of the law is $f$. We add type
annotations to the code as \emph{superscripts},
\[
\text{id}^{:A\rightarrow A}\bef f^{:A\rightarrow B}=\big(x^{:A}\rightarrow f(\text{id}\,(x))\big)^{:A\rightarrow B}\quad.
\]
In the Scala syntax, this formula may be written as
\begin{lstlisting}
id[A] andThen (f: A => B) == { x: A => f(id(x)) }: A => B
\end{lstlisting}

We will follow the convention where type parameters are single uppercase
letters, as is common in Scala code (although this convention is not
enforced by the Scala compiler). The colon symbol ($:$) in the superscript
$x^{:A}$ means a type annotation, as in Scala code \lstinline!x:A!.
Superscripts without a colon, such as $\text{id}^{A}$, denote type
parameters, as in Scala code \lstinline!identity[A]!. Since the function
\lstinline!identity[A]! has type \lstinline!A => A!, we can write
$\text{id}^{A}$ or equivalently (but more verbosely) $\text{id}^{:A\rightarrow A}$
to denote that function.

By definition of the identity function, we have $\text{id}\,(x)=x$,
and so 
\[
\text{id}\bef f=\left(x\rightarrow f(\text{id}\,(x))\right)=\left(x\rightarrow f(x)\right)=f\quad.
\]
The last step works since $x\rightarrow f(x)$ is a function taking
an argument $x$ and applying $f$ to that argument; i.e., $x\rightarrow f(x)$
is an \textbf{expanded form}\index{expanded form of a function} of
the same function $f$.

Now consider the right identity law, $f\bef\text{id}=f$. Write out
the left-hand side:
\[
f\bef\text{id}=\left(x\rightarrow\text{id}\,(f(x))\right)\quad.
\]
To check that the types match, assume that $f^{:A\rightarrow B}$.
Then $x$ must have type $A$, and the identity function must have
type $B\rightarrow B$. The result of $\text{id}\,(f(x))$ will also
have type $B$. With these choices of type parameters, all types match:
\[
f^{:A\rightarrow B}\bef\text{id}^{:B\rightarrow B}=\big(x^{:A}\rightarrow\text{id}\,(f(x))\big)^{:A\rightarrow B}\quad.
\]
Since $\text{id}\,(f(x))=f(x)$, we find that 
\[
f\bef\text{id}=\left(x\rightarrow f(x)\right)=f\quad.
\]
In this way, we have demonstrated that both identity laws hold. 

The associativity law is written as an equation like this:
\begin{align}
{\color{greenunder}\text{associativity law of function composition}:}\quad & (f\bef g)\bef h=f\bef(g\bef h)\quad.\label{eq:associativity-of-function-composition}
\end{align}
Let us verify that the types match here. The types of the functions
$f$, $g$, and $h$ must be such that all the function compositions
match. If $f$ has type $A\rightarrow B$ for some type parameters
$A$ and $B$, then the argument of $g$ must be of type $B$; so
we must have $g^{:B\rightarrow C}$, where $C$ is another type parameter.
The composition $f\bef g$ has type $A\rightarrow C$, so $h$ must
have type $C\rightarrow D$ for some type $D$. Assuming the types
as $f^{:A\rightarrow B}$, $g^{:B\rightarrow C}$, and $h^{:C\rightarrow D}$,
we find that the types in all the compositions $f\bef g$, $g\bef h$,
$(f\bef g)\bef h$, and $f\bef(g\bef h)$ match. We can rewrite Eq.~(\ref{eq:associativity-of-function-composition})
with type annotations, 
\begin{equation}
(f^{:A\rightarrow B}\bef g^{:B\rightarrow C})\bef h^{:C\rightarrow D}=f^{:A\rightarrow B}\bef(g^{:B\rightarrow C}\bef h^{:C\rightarrow D})\quad.\label{eq:associativity-law-for-function-composition-with-types}
\end{equation}

After checking the types, we are ready to verify the associativity
law. Note that both sides of the law~(\ref{eq:associativity-law-for-function-composition-with-types})
are functions of type $A\rightarrow D$. To prove that two functions
are equal means to prove that they always return the same results
when applied to the same arguments. So, let us apply both sides of
Eq.~(\ref{eq:associativity-law-for-function-composition-with-types})
to an arbitrary value $x^{:A}$. Using the definition~(\ref{eq:def-of-forward-composition})
of the forward composition, we find:
\begin{align*}
\left((f\bef g)\bef h\right)(x) & =h\left(\left(f\bef g\right)(x)\right)=h(g(f(x)))\quad,\\
\left(f\bef(g\bef h)\right)(x) & =\left(g\bef h\right)(f(x))=h(g(f(x)))\quad.
\end{align*}
Both sides of the law are now equal when applied to an arbitrary value
$x$.

Because of the associativity law, we do not need parentheses when
writing the expression $f\bef g\bef h$. The function $(f\bef g)\bef h$
is equal to the function $f\bef(g\bef h)$.

In the proof, we have omitted the type annotations since we already
checked that all types match. Checking the types beforehand allows
us to write shorter derivations.

\paragraph{Proofs with backward composition}

This book uses the \textbf{forward composition}\index{forward composition}
$f\bef g$ rather than the backward\index{backward composition} composition
$g\circ f$. If necessary, all equations can be converted from one
notation to the other by reversing the order of compositions,
\[
f\bef g=g\circ f
\]
for any functions $f^{:A\rightarrow B}$ and $g^{:B\rightarrow C}$.
Let us see how to prove the composition laws in the backward notation.
We will just need to reverse the order of function compositions in
the proofs above.

The left identity and right identity laws are
\[
f\circ\text{id}=f\quad\quad,\quad\text{id}\circ f=f\quad.
\]
To match the types, we need to choose the type parameters as
\[
f^{:A\rightarrow B}\circ\text{id}^{:A\rightarrow A}=f^{:A\rightarrow B}\quad\quad,\quad\text{id}^{B\rightarrow B}\circ f^{:A\rightarrow B}=f^{:A\rightarrow B}\quad.
\]
We now apply both sides of the laws to an arbitrary value $x^{:A}$.
For the left identity law, we find
\begin{align*}
{\color{greenunder}\text{use definition~(\ref{eq:def-of-backward-composition})}:}\quad & f\circ\text{id}=\left(x\rightarrow f(\text{id}\,(x))\right)=\left(x\rightarrow f(x)\right)=f\quad.
\end{align*}
Similarly for the right identity law,
\[
\text{id}\circ f=\left(x\rightarrow\text{id}\,(f(x))\right)=\left(x\rightarrow f\left(x\right)\right)=f\quad.
\]
The associativity law,
\[
h\circ\left(g\circ f\right)=\left(h\circ g\right)\circ f\quad,
\]
is proved by applying both sides to an arbitrary value $x$ of a suitable
type:
\begin{align*}
\left(h\circ\left(g\circ f\right)\right)(x) & =h\left(\left(g\circ f\right)(x)\right)=h\left(g\left(f\left(x\right)\right)\right)\quad,\\
\left(\left(h\circ g\right)\circ f\right)(x) & =\left(h\circ g\right)\left(f(x)\right)=h\left(g\left(f\left(x\right)\right)\right)\quad.
\end{align*}
The types are checked by assuming that $f$ has the type $f^{:A\rightarrow B}$.
The types in $g\circ f$ match only when $g^{:B\rightarrow C}$, and
then $g\circ f$ is of type $A\rightarrow C$. The type of $h$ must
be $h^{:C\rightarrow D}$ for the types in $h\circ\left(g\circ f\right)$
to match. We can write the associativity law with type annotations
as
\begin{equation}
h^{:C\rightarrow D}\circ(g^{:B\rightarrow C}\circ f^{:A\rightarrow B})=(h^{:C\rightarrow D}\circ g^{:B\rightarrow C})\circ f^{:A\rightarrow B}\quad.\label{eq:assoc-law-for-composition-with-types-backward}
\end{equation}
The associativity law allows us to omit parentheses in the expression
$h\circ g\circ f$. 

The length of calculations is the same in the forward and the backward
notation. One difference is that types of function compositions are
more visually clear in the forward notation: it is harder to check
that types match in Eq.~(\ref{eq:assoc-law-for-composition-with-types-backward})
than in Eq.~(\ref{eq:associativity-law-for-function-composition-with-types}).
To make the backward composition easier to work with, one could write\footnote{As in the book \textsf{``}Program design by calculation\textsf{''}, see \texttt{\href{http://www4.di.uminho.pt/~jno/ps/pdbc.pdf}{http://www4.di.uminho.pt/$\sim$jno/ps/pdbc.pdf}}}
the function types in reverse as, e.g., $g^{:C\leftarrow B}\circ f^{:B\leftarrow A}$.

\subsection{Example: A function that is \emph{not} fully parametric}

Fully parametric functions should not make any decisions based on
the actual types of arguments. As an example of code that is not fully
parametric, consider the following \textsf{``}fake identity\textsf{''} function:
\begin{lstlisting}
def fakeId[A]: A => A = {
  case x: Int   => (x - 1).asInstanceOf[A]     // Special code for A = Int.
  case x        =>  x                          // Common code for all other types A.
}
\end{lstlisting}
This function\textsf{'}s type signature is the same as that of \lstinline!id[A]!,
and its behavior is the same for all types \lstinline!A! except for
\lstinline!A = Int!:
\begin{lstlisting}
scala> fakeId("abc")
res0: String = abc

scala> fakeId(true)
res1: Boolean = true

scala> fakeId(0)
res2: Int = -1
\end{lstlisting}
While Scala allows us to write this kind of code, the resulting function
does not appear to be useful. In any case, \lstinline!fakeId! is
not a fully parametric function.

The identity laws of composition will not hold if we use \lstinline!fakeId[A]!
instead of the correct function \lstinline!id[A]!. For example, consider
the composition of \lstinline!fakeId! with a simple function \lstinline!f_1!
defined by
\begin{lstlisting}
def f_1: Int => Int = { x => x + 1 }
\end{lstlisting}
The composition (\lstinline!f_1 andThen fakeId!) has type \lstinline!Int => Int!.
Since \lstinline!f_1! has type \lstinline!Int => Int!, Scala will
automatically set the type parameter \lstinline!A = Int! in \lstinline!fakeId[A]!,
\begin{lstlisting}
scala> def f_2 = f_1 andThen fakeId
f_2: Int => Int
\end{lstlisting}
The identity law says that $f_{2}=f_{1}\bef\text{id}=f_{1}$. But
we can check that \lstinline!f_1! and \lstinline!f_2! are not the
same:

\begin{wrapfigure}{l}{0.18\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
scala> f_1(0)
res3: Int = 1

scala> f_2(0)
res4: Int = 0
\end{lstlisting}

\vspace{-0.8\baselineskip}
\end{wrapfigure}%

\noindent It is important that we are able to detect that \lstinline!fakeId!
is not a fully parametric function by checking whether some equation
holds, without need to examine the code of \lstinline!fakeId!. In
this book, we will always formulate the desired properties through
equations or \textsf{``}laws\textsf{''}. To verify that a law holds, we will perform
symbolic calculations\index{symbolic calculations} similar to the
proofs in Section~\ref{subsec:Laws-of-function-composition}. These
calculations are \textbf{symbolic} in the sense that we are manipulating
symbols (such as $x$, $f$, $g$, $h$) without substituting any
specific values for these symbols but using only the general properties
of functions. This is similar to symbolic calculations in polynomial
algebra, such as $\left(x-y\right)\left(x+y\right)=x^{2}-y^{2}$.
In the next section, we will get more experience with symbolic calculations
relevant to functional programming.

\section{Symbolic calculations with nameless functions}

\subsection{Calculations with curried functions}

In mathematics, functions are evaluated by substituting their argument
values into their body. Nameless functions are evaluated in the same
way. For example, applying the nameless function $x\rightarrow x+10$
to an integer $2$, we substitute $2$ instead of $x$ in \textquotedblleft $x+10$\textquotedblright{}
and get \textquotedblleft $2+10$\textquotedblright , which we then
evaluate to $12$. The computation is written like this, 
\[
(x\rightarrow x+10)(2)=2+10=12\quad.
\]
To run this computation in Scala, we need to add a type annotation
to the nameless function as in $(x^{:\text{Int}}\rightarrow x+10)(2)$:

\begin{wrapfigure}{l}{0.311\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
scala> ((x: Int) => x + 10)(2)
res0: Int = 12 
\end{lstlisting}

\vspace{-1.3\baselineskip}
\end{wrapfigure}%

\noindent Curried function calls such as $f(x)(y)$ or $\left(x\rightarrow\text{expr}(x)\right)(y)(z)$
may look unfamiliar and confusing; we need to gain some experience
working with them.

Consider a curried nameless function being applied to arguments, such
as \lstinline!(x => y => x - y)(20)(4)!, and compute the result of
this function application. Begin with the argument \lstinline!20!;
applying a nameless function of the form \lstinline!(x => ...)! to
\lstinline!20! means substituting \lstinline!x = 20! into the body
of the function. After that substitution, we obtain the expression
\lstinline!y => 20 - y!, which is again a nameless function. Applying
that function to the remaining argument \lstinline!(4)! means substituting
\lstinline!y = 4! into the body of \lstinline!y => 20 - y!. We get
the expression \lstinline!20 - 4!, which equals \lstinline!16!.
Check the result with Scala:
\begin{lstlisting}
scala> ((x: Int) => (y: Int) => x - y)(20)(4)
res1: Int = 16
\end{lstlisting}

Applying a curried function such as \lstinline!x => y => z => expr(x,y,z)!
to three curried arguments \lstinline!10!, \lstinline!20!, and \lstinline!30!
means substituting \lstinline!x = 10!, \lstinline!y = 20!, and \lstinline!z = 30!
into the expression \lstinline!expr(x,y,z)!. In this way, we can
easily apply a curried function to any number of curried arguments.

This calculation is helped by the convention that \lstinline!f(g)(h)!
means first applying \lstinline!f! to \lstinline!g! and then applying
the result to \lstinline!h!. In other words, function application
groups to the \emph{left}: \lstinline!f(g)(h) = (f(g))(h)!. It would
be confusing if function application grouped to the right and \lstinline!f(g)(h)!
meant first applying \lstinline!g! to \lstinline!h! and then applying
\lstinline!f! to the result. If \emph{that} were the syntax convention,
it would be harder to reason about applying a curried function to
its arguments.

We see that the right grouping of the function arrow \lstinline!=>!
is well adapted to the left grouping of function applications. All
functional languages follow these syntactic conventions.

To make calculations shorter, we will write code in a mathematical
notation rather than in the Scala syntax. Type annotations are written
with a colon in the superscript, for example: $x^{:\text{Int}}\rightarrow x+10$
instead of the code \lstinline!((x:Int) => x + 10)!.

The symbolic evaluation of the Scala code \lstinline!((x:Int) => (y:Int) => x - y)(20)(4)!
can be written as
\begin{align*}
 & (x^{:\text{Int}}\rightarrow y^{:\text{Int}}\rightarrow\gunderline x-y)\left(20\right)\left(4\right)\\
{\color{greenunder}\text{apply function and substitute }x=20:}\quad & =(y^{:\text{Int}}\rightarrow20-\gunderline y)\left(4\right)\\
{\color{greenunder}\text{apply function and substitute }y=4:}\quad & =20-4=16\quad.
\end{align*}
In the above step-by-step calculation, the colored underlines and
comments at left are added for clarity. A colored underline indicates
a sub-expression that is going to be rewritten at the \emph{next}
step.

Here we performed calculations by substituting an argument into a
function at each step. A compiled Scala program is evaluated in a
similar way at run time.

Nameless functions are \emph{values} and can be used as part of larger
expressions, just as any other values. For instance, nameless functions
can be arguments of other functions (nameless or not). Here is an
example of applying a nameless function $f\rightarrow f(9)$ to a
nameless function $x\rightarrow x\%\,4$:
\begin{align*}
 & (f\rightarrow\gunderline f(9))\left(x\rightarrow x\%\,4\right)\\
{\color{greenunder}\text{substitute }f=\left(x\rightarrow x\%\,4\right):}\quad & =(x\rightarrow\gunderline x\%\,4)(9)\\
{\color{greenunder}\text{substitute }x=9:}\quad & =9\%\,4=1\quad.
\end{align*}
In the nameless function $f\rightarrow f(9)$, the argument $f$ has
to be itself a function, otherwise the expression $f(9)$ would make
no sense. The argument $x$ of $f(x)$ must be an integer, or else
we would not be able to compute $x\%\,4$. The result of computing
$f(9)$ is $1$, an integer. We conclude that $f$ must have type
$\text{Int}\rightarrow\text{Int}$, or else the types will not match.
To verify this result in Scala, we need to specify a type annotation
for $f$:

\begin{wrapfigure}{l}{0.45\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
scala> ((f: Int => Int) => f(9))(x => x % 4)
res2: Int = 1
\end{lstlisting}
\vspace{-0.75\baselineskip}
\end{wrapfigure}%

\noindent No type annotation is needed for $x\rightarrow x\%\,4$
since the Scala compiler already knows the type of $f$ and figures
out that $x$ in $x\rightarrow x\%\,4$ must have type \lstinline!Int!.

To summarize the syntax conventions for curried nameless functions:
\begin{itemize}
\item Function expressions group everything to the right: $x\rightarrow y\rightarrow z\rightarrow e$
means $x\rightarrow\left(y\rightarrow\left(z\rightarrow e\right)\right)$.
\item Function calls group everything to the left. So, $f(x)(y)(z)$ means
$\big((f(x))(y)\big)(z)$, i.e., $f(x)$ gives a new function that
is applied to $y$, giving again a new function that is finally applied
to $z$.
\item Function applications group stronger than infix operations, so $f(x)+y$
means $(f(x))+y$, as usual in mathematics, and not $f(x+y)$.
\end{itemize}
Here are some more examples of performing function applications symbolically.
Types are omitted for brevity; every non-function value is of type
\texttt{}\lstinline!Int!.
\begin{align*}
\left(x\rightarrow x*2\right)(10) & =10*2=20\quad.\\
\left(p\rightarrow z\rightarrow z*p\right)\left(t\right) & =(z\rightarrow z*t)\quad.\\
\left(p\rightarrow z\rightarrow z*p\right)(t)(4) & =(z\rightarrow z*t)(4)=4*t\quad.
\end{align*}
Some results of these computation are integer values such as $20$;
other results are nameless functions such as $z\rightarrow z*t$.
Verify this in Scala:
\begin{lstlisting}
scala> ((x:Int) => x*2)(10)
res3: Int = 20

scala> ((p:Int) => (z:Int) => z*p)(10)
res4: Int => Int = <function1>

scala> ((p:Int) => (z:Int) => z*p)(10)(4)
res5: Int = 40 
\end{lstlisting}

In the following examples, some arguments are themselves functions.
Consider an expression that uses the nameless function $\left(g\rightarrow g(2)\right)$
as an argument:
\begin{align}
 & (f\rightarrow p\rightarrow\gunderline f(p))\left(g\rightarrow g(2)\right)\label{eq:higher-order-functions-derivation0}\\
{\color{greenunder}\text{substitute }f=\left(g\rightarrow g(2)\right):}\quad & =p\rightarrow(g\rightarrow\gunderline g(2))\,(p)\nonumber \\
{\color{greenunder}\text{substitute }g=p:}\quad & =p\rightarrow p(2)\quad.\label{eq:higher-order-functions-derivation1}
\end{align}
The result of this expression is a function $p\rightarrow p(2)$ that
will apply \emph{its} argument $p$ to the value $2$. A possible
value for $p$ is the function $x\rightarrow x+4$. So, let us apply
the expression in Eq.~(\ref{eq:higher-order-functions-derivation0})
to $p\rightarrow p(2)$:
\begin{align*}
 & \gunderline{\left(f\rightarrow p\rightarrow f(p)\right)\left(g\rightarrow g(2)\right)}\left(x\rightarrow x+4\right)\\
{\color{greenunder}\text{use Eq.~(\ref{eq:higher-order-functions-derivation1})}:}\quad & =(p\rightarrow\gunderline p(2))\left(x\rightarrow x+4\right)\\
{\color{greenunder}\text{substitute }p=\left(x\rightarrow x+4\right):}\quad & =(x\rightarrow\gunderline x+4)\left(2\right)\\
{\color{greenunder}\text{substitute }x=2:}\quad & =2+4=6\quad.
\end{align*}

To verify this calculation in Scala, we need to add appropriate type
annotations for $f$ and $p$. To figure out the types, we reason
like this:

We know that the function $f\rightarrow p\rightarrow f(p)$ is being
applied to the arguments $f=\left(g\rightarrow g(2)\right)$ and $p=\left(x\rightarrow x+4\right)$.
So, the argument $f$ in $f\rightarrow p\rightarrow f(p)$ must be
a function that takes $p$ as an argument.

The variable $x$ in $x\rightarrow x+4$ must be of type \lstinline!Int!.
Thus, the type of the expression $x\rightarrow x+4$ is $\text{Int}\rightarrow\text{Int}$,
and so must be the type of the argument $p$. We write $p^{:\text{Int}\rightarrow\text{Int}}$.

Finally, we need to make sure that the types match in the function
$f\rightarrow p\rightarrow f(p)$. Types match in $f(p)$ if the type
of $f$\textsf{'}s argument is the same as the type of $p$, which is $\text{Int}\rightarrow\text{Int}$.
So $f$\textsf{'}s type must be $\left(\text{Int}\rightarrow\text{Int}\right)\rightarrow A$
for some type $A$. Since in our example $f=\left(g\rightarrow g(2)\right)$,
types match only if $g$ has type $\text{Int}\rightarrow\text{Int}$.
But then $g(2)$ has type $\text{Int}$, and so we must have $A=\text{Int}$.
Thus, the type of $f$ is $\left(\text{Int}\rightarrow\text{Int}\right)\rightarrow\text{Int}$.
We know enough to write the Scala code now:

\begin{wrapfigure}{l}{0.69\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
scala> ((f: (Int => Int) => Int) => p => f(p))(g => g(2))(x => x + 4)
res6: Int = 6
\end{lstlisting}
\vspace{-1\baselineskip}
\end{wrapfigure}%

\noindent Type annotations for $p$, $g$, and $x$ may be omitted
because the Scala compiler will figure out the missing types from
the given type of $f$. However, it is never an error to specify more
type annotations when writing code; it just makes the code longer.

\subsection{Solved examples: Deriving a function\textsf{'}s type from its code\index{solved examples}}

Checking that the types match is an important part of the functional
programming paradigm, both in the practice of writing code and in
theoretical derivations of laws for various functions. For instance,
in the derivations of the composition laws (Section~\ref{subsec:Laws-of-function-composition}),
we were able to deduce the possible type parameters for $f$, $g$,
and $h$ in the expression $f\bef g\bef h$. This worked because the
composition operation \lstinline!andThen! (denoted by the symbol
$\bef$) is fully parametric. Given a fully parametric function, one
can derive the most general type signature that matches the body of
that function. The same type-deriving procedure may also help in converting
a given function to a fully parametric form.

Let us look at some examples of doing this.

\subsubsection{Example \label{subsec:Example-hof-derive-types-1}\ref{subsec:Example-hof-derive-types-1}}

The functions \lstinline!const! and \lstinline!id! were defined
in Section~\ref{subsec:Examples-of-fully-parametric}. What is the
value \lstinline!const(id)! and what is its type? Determine the most
general type parameters in the expression \lstinline!const(id)!.

\subparagraph{Solution}

We need to treat the functions \lstinline!const! and \lstinline!id!
as values, since our goal is to apply \lstinline!const! to \lstinline!id!.
Write the code of these functions in a short notation:
\begin{align*}
\text{const}^{C,X} & \triangleq c^{:C}\rightarrow\_^{:X}\rightarrow c\quad,\\
\text{id}^{A} & \triangleq a^{:A}\rightarrow a\quad.
\end{align*}
The types will match in the expression \lstinline!const(id)! only
if the argument of the function \lstinline!const! has the same type
as the type of \lstinline!id!. Since \lstinline!const! is a curried
function, we need to look at its \emph{first} curried argument, which
is of type $C$. The type of \lstinline!id! is $A\rightarrow A$,
where $A$ is so far an arbitrary type. So, the type parameter $C$
in $\text{const}^{C,X}$ must be equal to $A\rightarrow A$:
\[
C=A\rightarrow A\quad.
\]
 The type parameter $X$ in $\text{const}^{C,X}$ is not constrained,
so we keep it as $X$. The result of applying \lstinline!const! to
\lstinline!id! is of type $X\rightarrow C$, which equals $X\rightarrow A\rightarrow A$.
In this way, we find 
\[
\text{const}^{A\rightarrow A,X}(\text{id}^{A}):X\rightarrow A\rightarrow A\quad.
\]
The types $A$ and $X$ can be arbitrary. The type $X\rightarrow A\rightarrow A$
is the most general type for the expression \lstinline!const(id)!
because we have not made any assumptions about the types except requiring
that all functions must be always applied to arguments of the correct
types.

To compute the value of \lstinline!const(id)!, it remains to substitute
the code of \lstinline!const! and \lstinline!id!. Since we already
checked the types, we may omit all type annotations:
\begin{align*}
 & \gunderline{\text{const}}\left(\text{id}\right)\\
{\color{greenunder}\text{definition of const}:}\quad & =(c\rightarrow x\rightarrow\gunderline c)(\text{id})\\
{\color{greenunder}\text{apply function, substitute }c=\text{id}:}\quad & =x\rightarrow\gunderline{\text{id}}\\
{\color{greenunder}\text{definition of }\text{id}:}\quad & =x\rightarrow a\rightarrow a\quad.
\end{align*}

The function $\left(x\rightarrow a\rightarrow a\right)$ takes an
argument $x^{:X}$ and returns the identity function $a^{:A}\rightarrow a$.
It is clear that the argument $x$ is ignored by this function, so
we can rewrite it equivalently as
\[
\text{const}\left(\text{id}\right)=\_^{:X}\rightarrow a^{:A}\rightarrow a\quad.
\]


\subsubsection{Example \label{subsec:Example-hof-derive-types-2}\ref{subsec:Example-hof-derive-types-2}}

Implement a function \lstinline!twice! that takes a function \lstinline!f: Int => Int!
as its argument and returns a function that applies \lstinline!f!
twice. For instance, if the function \lstinline!f! is \lstinline!{ x => x + 3 }!,
the result of \lstinline!twice(f)! should be equal to the function
\lstinline!x => x + 6!. Test this with the expression \lstinline!twice(x => x + 3)(10)!.
After implementing the function \lstinline!twice!, generalize it
to a fully parametric function.

\subparagraph{Solution}

According to the requirements, the function \lstinline!twice! must
return a new function of type \lstinline!Int => Int!. So the type
signature of \lstinline!twice! is
\begin{lstlisting}
def twice(f: Int => Int): Int => Int = ???
\end{lstlisting}
Since \lstinline!twice(f)! must be a new function with an integer
argument, we begin the code of \lstinline!twice! by writing a new
nameless function \lstinline!{ (x: Int) => ... }!,
\begin{lstlisting}
def twice(f: Int => Int): Int => Int = { (x: Int) => ??? }
\end{lstlisting}
The new function must apply \lstinline!f! twice to its argument,
that is, it must return \lstinline!f(f(x))!. We can finish the implementation
now:
\begin{lstlisting}
def twice(f: Int => Int): Int => Int = { x => f(f(x)) }
\end{lstlisting}
The type annotation \lstinline!(x: Int)! can be omitted. Let us verify
that \lstinline!twice(x => x+3)(10)! equals \lstinline!10 + 6!:
\begin{lstlisting}
scala> val g = twice(x => x + 3)  // Expect g to be equal to the function { x => x + 6 }.
g: Int => Int = <function1>

scala> g(10)                      // Expect twice(x => x + 3)(10) to be equal to (x => x+6)(10) = 16.
res0: Int = 16
\end{lstlisting}

To transform \lstinline!twice! into a fully parametric function means
replacing its type signature by a fully parameterized type signature
while keeping the function body unchanged,

\begin{wrapfigure}{l}{0.525\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
def twice[A, B, ...](f: ...): ... = { x => f(f(x)) }
\end{lstlisting}
\vspace{-1\baselineskip}
\end{wrapfigure}%

\noindent To determine the type signature and the possible type parameters
$A$, $B$, ..., we need to determine the most general type that matches
the function body. The function body is the expression $x\rightarrow f(f(x))$.
Assume that $x$ has type $A$; for types to match in the sub-expression
$f(x)$, we need $f$ to have type $A\rightarrow B$ for some type
$B$. The sub-expression $f(x)$ will then have type $B$. For types
to match in $f(f(x))$, the argument of $f$ must have type $B$;
but we already assumed $f^{:A\rightarrow B}$. This is consistent
only if $A=B$. In this way, $x^{:A}$ implies $f^{:A\rightarrow A}$,
and the expression $x\rightarrow f(f(x))$ has type $A\rightarrow A$.
We can now write the type signature of \lstinline!twice!,

\begin{wrapfigure}{l}{0.51\columnwidth}%
\vspace{-0.75\baselineskip}
\begin{lstlisting}
def twice[A](f: A => A): A => A = { x => f(f(x)) }
\end{lstlisting}
\vspace{-0.95\baselineskip}
\end{wrapfigure}%

\noindent This fully parametric function has only one independent
type parameter, $A$, and can be equivalently written in the code
notation as 
\begin{equation}
\text{twice}^{A}\triangleq f^{:A\rightarrow A}\rightarrow x^{:A}\rightarrow f(f(x))=f^{:A\rightarrow A}\rightarrow f\bef f\quad.\label{eq:hof-def-of-twice-in-math-notation}
\end{equation}

The procedure of deriving the most general type for a given code is
called \textbf{type inference}\index{type inference|textit}. In Example~\ref{subsec:Example-hof-derive-types-2},
the presence of the type parameter $A$ and the type signature $\left(A\rightarrow A\right)\rightarrow A\rightarrow A$
have been \textsf{``}inferred\textsf{''} from the code $f\rightarrow x\rightarrow f(f(x))$.

\subsubsection{Example \label{subsec:Example-hof-derive-types-3}\ref{subsec:Example-hof-derive-types-3}}

Consider the fully parametric function \lstinline!twice! defined
in Example~\ref{subsec:Example-hof-derive-types-2}. What is the
most general type of \lstinline!twice(twice)!, and what computation
does it perform? Test your answer on the expression \lstinline!twice(twice)(x => x+3)(10)!.
What are the type parameters in that expression?

\subparagraph{Solution}

Note that \lstinline!twice(twice)! means that the function \lstinline!twice!
is used as \emph{its own} argument, i.e., this is \lstinline!twice(f)!
with \lstinline!f = twice!. We begin by assuming unknown type parameters
as \lstinline!twice[A](twice[B])!. The function \lstinline!twice[A]!
of type $\left(A\rightarrow A\right)\rightarrow A\rightarrow A$ can
be applied to the argument \lstinline!twice[B]! only if \lstinline!twice[B]!
has type $A\rightarrow A$. But \lstinline!twice[B]! is of type $\left(B\rightarrow B\right)\rightarrow B\rightarrow B$.
The symbol $\rightarrow$ groups to the right, so we have
\[
\left(B\rightarrow B\right)\rightarrow B\rightarrow B=\left(B\rightarrow B\right)\rightarrow\left(B\rightarrow B\right)\quad.
\]
This can match with $A\rightarrow A$ only if we set $A=\left(B\rightarrow B\right)$.
So the most general type of \lstinline!twice(twice)! is
\begin{equation}
\text{twice}^{B\rightarrow B}(\text{twice}^{B}):\left(B\rightarrow B\right)\rightarrow B\rightarrow B\quad.\label{eq:hof-twice-example-solved3}
\end{equation}
After checking that types match, we may omit types from further calculations.

Example~\ref{subsec:Example-hof-derive-types-2} defined \lstinline!twice!
with the \lstinline!def! syntax. To use \lstinline!twice! as an
argument in the expression \lstinline!twice(twice)!, it is convenient
to define \lstinline!twice! as a value, \lstinline!val twice = ...!
However, the function \lstinline!twice! needs type parameters, and
Scala 2 does not directly support \lstinline!val! definitions with
type parameters. Scala 3 will support type parameters appearing together
with arguments in a nameless function:
\begin{lstlisting}
val twice = [A] => (f: A => A) => (x: A) => f(f(x)) // Valid only in Scala 3.
\end{lstlisting}
Keeping this in mind, we use the definition of \lstinline!twice!
from Eq.~(\ref{eq:hof-def-of-twice-in-math-notation}): $\text{twice}\,(f)=f\bef f$,
which omits the curried argument $x^{:A}$ and makes the calculation
shorter. Substituting that into \lstinline!twice(twice)!, we find
\begin{align*}
 & \text{twice}\,(\text{twice})=\text{twice}\bef\text{twice}\\
{\color{greenunder}\text{expand function composition}:}\quad & =f\rightarrow\text{twice}\,(\gunderline{\text{twice}}\,(f))\quad.\\
{\color{greenunder}\text{definition of }\text{twice}\,(f):}\quad & =f\rightarrow\gunderline{\text{twice}}\,(f\bef f)\\
{\color{greenunder}\text{definition of twice}:}\quad & =f\rightarrow f\bef f\bef f\bef f\quad.
\end{align*}
This clearly shows that \lstinline!twice(twice)! is a function applying
its (function-typed) argument \emph{four} times.

The types in \lstinline!twice(twice)(x => x+3)! follow from Eq.~(\ref{eq:hof-twice-example-solved3}):
since \lstinline!x => x+3! has type \lstinline!Int => Int!, types
will match only if we set $B=\text{Int}$. The result is \lstinline!twice[Int => Int](twice[Int])!.
To test, we need to write at least one type parameter in the code,
or else Scala cannot correctly infer the types in \lstinline!twice(twice)!:
\begin{lstlisting}
scala> twice(twice[Int])(x => x + 3)(10) // Or write `twice[Int => Int](twice)(x => x + 3)(10)` .
res0: Int = 22
\end{lstlisting}
This confirms that \lstinline!twice(twice)(x => x+3)! equals the
function \lstinline!x => x + 12!, unlike \lstinline!twice(twice(x => x+3))!,
which equals the function \lstinline!x => x + 6! as shown in Example~\ref{subsec:Example-hof-derive-types-2}.

\subsubsection{Example \label{subsec:Example-hof-derive-types-4}\ref{subsec:Example-hof-derive-types-4}}

\textbf{(a)} For the given function \lstinline!p!, infer a general
type signature with type parameter(s):
\begin{lstlisting}
def p[...]:... = { f => f(2) }
\end{lstlisting}
\textbf{(b)} Could we choose the type parameters in the expression
\lstinline!p(p)! such that the types match?

\subparagraph{Solution}

\textbf{(a)} In the nameless function $f\rightarrow f(2)$, the argument
$f$ must be itself a function with an argument of type \lstinline!Int!,
otherwise the sub-expression $f(2)$ is ill-typed. So, types will
match if $f$ has type $\text{Int}\rightarrow\text{Int}$ or $\text{Int}\rightarrow\text{String}$
or similar. The most general case is when $f$ has type $\text{Int}\rightarrow A$,
where $A$ is an arbitrary type (i.e., a type parameter); then the
value $f(2)$ has type $A$. Since the nameless function $f\rightarrow f(2)$
has an argument $f$ of type $\text{Int}\rightarrow A$ and a result
$f(2)$ of type $A$, we find that the type of $p$ must be $\left(\text{Int}\rightarrow A\right)\rightarrow A$.
With this type assignment, all types match. The type parameter $A$
remains undetermined and is added to the type signature of the function
\lstinline!p!. The code is
\begin{lstlisting}
def p[A]: (Int => A) => A = { f => f(2) }
\end{lstlisting}

\textbf{(b)} The expression \lstinline!p(p)! applies \lstinline!p!
to itself, just as \lstinline!twice(twice)! did in Example~\ref{subsec:Example-hof-derive-types-3}.
Begin by writing \lstinline!p(p)! with unknown type parameters: \lstinline!p[A](p[B])!.
Then  try to choose \lstinline!A! and \lstinline!B! so that the
types match in that expression. Does the type of \lstinline!p[B]!,
which is \lstinline!(Int => B) => B!, match the type of the argument
of \lstinline!p[A]!, which is \lstinline!Int => A!, with some choice
of \lstinline!A! and \lstinline!B!? A function type \lstinline!P => Q!
matches \lstinline!X => Y! only if \lstinline!P = X! and \lstinline!Q = Y!.
So \lstinline!(Int => B) => B! can match \lstinline!Int => A! only
if \lstinline!Int => B! matches \lstinline!Int! and if \lstinline!B = A!.
But it is impossible for \lstinline!Int => B! to match \lstinline!Int!,
no matter how we choose \lstinline!B!. 

We conclude that the expression \lstinline!p[A](p[B])! has a problem:
for any choice of \lstinline!A! and \lstinline!B!, some type will
be mismatched. One says that the expression \lstinline!p(p)! is \textbf{not
well-typed}\index{well-typed expression} and does not \textbf{typecheck}\index{type checking}.
Such expressions contain a type error and are rejected by the Scala
compiler. 

We have seen that, for a code fragment containing  function expressions,
one can infer the most general type that makes all functions match
their arguments, unless the code does not typecheck. The Damas-Hindley-Milner
algorithm\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Hindley\%E2\%80\%93Milner_type_system\#Algorithm_W}{https://en.wikipedia.org/wiki/Hindley\%E2\%80\%93Milner\_type\_system\#Algorithm\_W}}}
performs type inference\index{type inference} (or determines that
there is a type error) for a large class of expressions containing
functions, tuples, and disjunctive types.

\section{Summary}

\begin{table}
\begin{centering}
\begin{tabular}{|c|c|c|}
\hline 
\textbf{\small{}Notation} & \textbf{\small{}Scala syntax} & \textbf{\small{}Comments}\tabularnewline
\hline 
\hline 
{\small{}$x^{:A}$} & {\small{}}\lstinline!x: A! & {\small{}a value or an argument of type }\lstinline!A!\tabularnewline
\hline 
{\small{}$f^{:A\rightarrow B}$} & {\small{}}\lstinline!f: A => B! & {\small{}a function of type }\lstinline!A => B!\tabularnewline
\hline 
{\small{}$x^{:\text{Int}}\rightarrow f(x)$} & {\small{}}\lstinline!{ x: Int => f(x) }! & {\small{}a nameless function with argument }\lstinline!x!\tabularnewline
\hline 
{\small{}$f^{A,B}\triangleq...$} & {\small{}}\lstinline!def f[A, B] = ...! & {\small{}define a function with type parameters}\tabularnewline
\hline 
{\small{}$\text{id}^{A}$, also $\text{id}^{:A\rightarrow A}$} & {\small{}}\lstinline!identity[A]! & {\small{}the standard \textsf{``}identity\textsf{''} function}\tabularnewline
\hline 
{\small{}$A\rightarrow B\rightarrow C$} & {\small{}}\lstinline!A => B => C! & {\small{}type of a curried function}\tabularnewline
\hline 
{\small{}$f\bef g$} & {\small{}}\lstinline!f andThen g! & {\small{}forward composition of functions}\tabularnewline
\hline 
{\small{}$g\circ f$} & {\small{}}\lstinline!g compose f! & {\small{}backward composition of functions}\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\caption{Some notation for symbolic reasoning about code.\label{tab:Mathematical-notation-for-code}}
\end{table}
Table~\ref{tab:Mathematical-notation-for-code} shows the notations
introduced in this chapter. 

What can we do with this chapter\textsf{'}s techniques?
\begin{itemize}
\item Implement functions that return new functions and/or take functions
as arguments.
\item Simplify function expressions symbolically, when functions are applied
to arguments.
\item Infer the most general type for a given code expression (perform type
inference).
\item Convert functions to a fully parametric form when possible.
\end{itemize}
The following solved examples and exercises illustrate these techniques.

\subsection{Solved examples\index{solved examples}}

\subsubsection{Example \label{subsec:Example-hof-simple-1}\ref{subsec:Example-hof-simple-1}}

Implement a function that applies a given function $f$ repeatedly
to an initial value $x_{0}$, until a given function \lstinline!cond!
returns \lstinline!true!:
\begin{lstlisting}
def converge[X](f: X => X, x0: X, cond: X => Boolean): X = ???
\end{lstlisting}


\subparagraph{Solution}

We create an iterator that keeps applying the function $f$, and use
\lstinline!find! to stop the sequence when the condition first holds:
\begin{lstlisting}
def converge[X](f: X => X, x0: X, cond: X => Boolean): X = 
  Stream.iterate(x0)(f)   // Type is Stream[X].
  .find(cond)             // Type is Option[X].
  .get                    // Type is X.
\end{lstlisting}
The method \lstinline!get! is a \index{partial function}partial
function that can be applied only to non-empty \lstinline!Option!
values. It is safe to call \lstinline!get! here, because the stream
is unbounded and, if the condition \lstinline!cond! never becomes
\lstinline!true!, the program will run out of memory (since \lstinline!Stream.iterate!
keeps all computed values in memory) or the user will run out of patience.
So \lstinline!.find(cond)! can never return an empty \lstinline!Option!
value. Of course, it is not satisfactory that the program crashes
when the sequence does not converge. Exercise~\ref{subsec:Exercise-hof-simple-8}
will implement a safer version of this function by limiting the allowed
number of iterations.

A tail-recursive implementation that works in constant memory is 
\begin{lstlisting}
@tailrec def converge[X](f: X => X, x0: X, cond: X => Boolean): X =
  if (cond(x0)) x0 else converge(f, f(x0), cond)
\end{lstlisting}
To test this code, compute an approximation to $\sqrt{q}$ by Newton\textsf{'}s
method\index{Newton\textsf{'}s method}. The iteration function $f$ is 
\[
f(x)=\frac{1}{2}\left(x+\frac{q}{x}\right)\quad.
\]
We iterate $f(x)$ starting with $x_{0}=q/2$ until we obtain a given
precision:
\begin{lstlisting}
def approx_sqrt(q: Double, precision: Double): Double = {
      def cond(x: Double): Boolean = math.abs(x * x - q) <= precision
      def iterate_sqrt(x: Double): Double = 0.5 * (x + q / x)
      converge(iterate_sqrt, q / 2, cond)
}
\end{lstlisting}
Newton\textsf{'}s method for $\sqrt{q}$ is guaranteed to converge when $q\geq0$.
Test it:
\begin{lstlisting}
scala> approx_sqrt(25, 1.0e-8)
res0: Double = 5.000000000016778
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-hof-simple-2}\ref{subsec:Example-hof-simple-2}}

Using both \lstinline!def! and \lstinline!val!, define a Scala function
that takes an integer \lstinline!x! and returns a function that adds
\lstinline!x! to \emph{its} argument.

\subparagraph{Solution}

Let us first write down the required type signature: the function
must take an integer argument \lstinline!x: Int!, and the return
value must be a function of type \lstinline!Int => Int!.
\begin{lstlisting}
def add_x(x: Int): Int => Int = ???
\end{lstlisting}
We are required to return a function that adds \lstinline!x! to its
argument. Let us call that argument \lstinline!z!, to avoid confusion
with the \lstinline!x!. So, we are required to return the function
\lstinline!{ z => z + x }!. Since functions are values, we return
a new function by writing a nameless function expression:
\begin{lstlisting}
def add_x(x: Int): Int => Int = { z => z + x }
\end{lstlisting}
To implement the same function by using a \lstinline!val!, we first
convert the type signature of \lstinline!add_x! to the equivalent
curried type $\text{Int}\rightarrow\text{Int}\rightarrow\text{Int}$.
Now we can write the Scala code of a function \lstinline!add_x_v!:
\begin{lstlisting}
val add_x_v: Int => Int => Int = { x => z => z + x }
\end{lstlisting}
The function \lstinline!add_x_v! is equal to \lstinline!add_x! except
for using the \lstinline!val! syntax instead of \lstinline!def!.
It is not necessary to specify the type of the arguments \lstinline!x!
and \lstinline!z! because we already specified the type $\text{Int}\rightarrow\text{Int}\rightarrow\text{Int}$
for the value \lstinline!add_x_v!. 

\subsubsection{Example \label{subsec:Example-hof-simple-3}\ref{subsec:Example-hof-simple-3}}

Using both \lstinline!def! and \lstinline!val!, implement a curried
function \lstinline!prime_f! that takes a function $f$ and an integer
$x$, and returns \lstinline!true! when $f(x)$ is a prime number.
Use the function \lstinline!isPrime! defined in Section~\ref{subsec:Nameless-functions}. 

\subparagraph{Solution}

First, determine the required type signature of \lstinline!prime_f!.
The value $f(x)$ must have type \lstinline!Int!, or else we cannot
check whether it is prime. So, $f$ must have type $\text{Int}\rightarrow\text{Int}$.
Since \lstinline!prime_f! should be a curried function, we need to
put each argument into its own set of parentheses:
\begin{lstlisting}
def prime_f(f: Int => Int)(x: Int): Boolean = ???
\end{lstlisting}
To implement \lstinline!prime_f!, we need to return the result of
\lstinline!isPrime! applied to \lstinline!f(x)!. A simple solution
is
\begin{lstlisting}
def prime_f(f: Int => Int)(x: Int): Boolean = isPrime(f(x))
\end{lstlisting}

To implement the same function as a \lstinline!val!, rewrite its
type signature as
\begin{lstlisting}
val prime_f: (Int => Int) => Int => Boolean = ???
\end{lstlisting}
(The parentheses around \lstinline!Int => Int! are mandatory since
\lstinline!Int => Int => Int => Boolean! would be a completely different
type.) The implementation is
\begin{lstlisting}
val prime_f: (Int => Int) => Int => Boolean = { f => x => isPrime(f(x)) }
\end{lstlisting}
The code \lstinline!isPrime(f(x))! is a forward composition of the
functions \lstinline!f! and \lstinline!isPrime!, so we can write
\begin{lstlisting}
val prime_f: (Int => Int) => Int => Boolean = (f => f andThen isPrime)
\end{lstlisting}
A nameless function of the form \lstinline!f => f.something! is equivalent
to a shorter Scala syntax \lstinline!(_.something)!. So we finally
rewrite the code of \lstinline!prime_f! as
\begin{lstlisting}
val prime_f: (Int => Int) => Int => Boolean = (_ andThen isPrime)
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-hof-simple-4}\ref{subsec:Example-hof-simple-4}}

Implement a function \lstinline!choice(x,p,f,g)! that takes a value
$x$, a predicate $p$, and two functions $f$ and $g$. The return
value must be $f(x)$ if $p(x)$ returns \lstinline!true!; otherwise
the return value must be $g(x)$. Infer the most general type for
this function.

\subparagraph{Solution}

The code of this function must be
\begin{lstlisting}
def choice[...](x,p,f,g) = if (p(x)) f(x) else g(x)
\end{lstlisting}
To infer the most general type for this code, begin by assuming that
$x$ has type $A$, where $A$ is a type parameter. Then the predicate
$p$ must have type \lstinline!A => Boolean!. Since $p$ is an arbitrary
predicate, the value $p(x)$ will be sometimes \lstinline!true! and
sometimes \lstinline!false!. So, \lstinline!choice(x,p,f,g)! will
sometimes compute $f(x)$ and sometimes $g(x)$. It follows that type
$A$ must be the argument type of both $f$ and $g$, which means
that the most general types so far are $f^{:A\rightarrow B}$ and
$g^{:A\rightarrow C}$, yielding the type signature
\[
\text{choice}(x^{:A},p^{:A\rightarrow\text{Boolean}},f^{:A\rightarrow B},g^{:A\rightarrow C})\quad.
\]

What could be the return type of \lstinline!choice(x,p,f,g)!? If
$p(x)$ returns \lstinline!true!, the function \lstinline!choice!
returns $f(x)$, which is of type $B$. Otherwise, \lstinline!choice!
returns $g(x)$, which is of type $C$. However, the type signature
of \lstinline!choice! must be fixed in advance (at compile time)
and cannot depend on the value $p(x)$ computed at run time. So, the
types of $f(x)$ and of $g(x)$ must be the same, $B=C$. The type
signature of \lstinline!choice! will thus have only two type parameters,
$A$ and $B$:
\begin{lstlisting}
def choice[A, B](x: A, p: A => Boolean, f: A => B, g: A => B): B =  if (p(x)) f(x) else g(x)
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-hof-derive-types-5}\ref{subsec:Example-hof-derive-types-5}}

Infer the most general type for the fully parametric function
\begin{lstlisting}
def q[...]: ... = { f => g => g(f) }
\end{lstlisting}
What types are inferred for the expressions \lstinline!q(q)! and
\lstinline!q(q(q))!?

\subparagraph{Solution}

Begin by assuming $f^{:A}$ with a type parameter $A$. In the sub-expression
$g\rightarrow g(f)$, the curried argument $g$ must itself be a function,
because it is being applied to $f$ as $g(f)$. So we assign types
as $f^{:A}\rightarrow g^{:A\rightarrow B}\rightarrow g(f)$, where
$A$ and $B$ are type parameters. Then the final returned value $g(f)$
has type $B$. Since there are no other constraints on the types,
the types $A$ and $B$ remain arbitrary, so we add them to the type
signature:
\begin{lstlisting}
def q[A, B]: A => (A => B) => B = { f => g => g(f) }
\end{lstlisting}

To match types in the expression \lstinline!q(q)!, we first assume
arbitrary type parameters and write \lstinline!q[A, B](q[C, D])!.
We need to introduce new type parameters $C$, $D$ because these
type parameters may need to be set differently from $A$, $B$ when
we try to match the types in the expression \lstinline!q(q)!.

The type of the first curried argument of \lstinline!q[A, B]!, which
is $A$, must match the entire type of \lstinline!q[C, D]!, which
is $C\rightarrow\left(C\rightarrow D\right)\rightarrow D$. So we
must set the type parameter $A$ as
\[
A=C\rightarrow\left(C\rightarrow D\right)\rightarrow D\quad.
\]
The type of \lstinline!q(q)! becomes
\[
q^{A,B}(q^{C,D}):\left(\left(C\rightarrow\left(C\rightarrow D\right)\rightarrow D\right)\rightarrow B\right)\rightarrow B\quad,\quad\text{where}\quad A=C\rightarrow\left(C\rightarrow D\right)\rightarrow D\quad.
\]
There are no other constraints on the type parameters $B$, $C$,
$D$.

We use this result to infer the most general type for \lstinline!q(q(q))!.
We may denote $r\triangleq q(q)$ for brevity; then, as we just found,
$r$ has type $\left(\left(C\rightarrow\left(C\rightarrow D\right)\rightarrow D\right)\rightarrow B\right)\rightarrow B$.
To infer types in the expression \lstinline!q(r)!, we introduce new
type parameters $E$, $F$ and write \lstinline!q[E, F](r)!. The
type of the argument of \lstinline!q[E, F]! is $E$, and this must
be the same as the type of $r$. This gives the constraint
\[
E=\left(\left(C\rightarrow\left(C\rightarrow D\right)\rightarrow D\right)\rightarrow B\right)\rightarrow B\quad.
\]
Other than that, the type parameters are arbitrary. The type of the
expression \lstinline!q(q(q))! is $\left(E\rightarrow F\right)\rightarrow F$.
We conclude that the most general type of \lstinline!q(q(q))! is
\begin{align*}
q^{E,F}(q^{A,B}(q^{C,D})) & :\left(\left(\left(\left(C\rightarrow\left(C\rightarrow D\right)\rightarrow D\right)\rightarrow B\right)\rightarrow B\right)\rightarrow F\right)\rightarrow F\quad,\\
\text{where}\quad & A=C\rightarrow\left(C\rightarrow D\right)\rightarrow D\\
\text{and}\quad & E=\left(\left(C\rightarrow\left(C\rightarrow D\right)\rightarrow D\right)\rightarrow B\right)\rightarrow B\quad.
\end{align*}
It is clear from this derivation that expressions such as \lstinline!q(q(q(q)))!,
\lstinline!q(q(q(q(q))))!, etc., are well-typed.

Let us test these results in Scala, renaming the type parameters for
clarity to \lstinline!A!, \lstinline!B!, \lstinline!C!, \lstinline!D!:
\begin{lstlisting}
scala> def qq[A, B, C]: ((A => (A => B) => B) => C) => C = q(q)
qq: [A, B, C]=> ((A => ((A => B) => B)) => C) => C

scala> def qqq[A, B, C, D]: ((((A => (A => B) => B) => C) => C) => D) => D = q(q(q))
qqq: [A, B, C, D]=> ((((A => ((A => B) => B)) => C) => C) => D) => D
\end{lstlisting}
We did not need to write any type parameters within the expressions
\lstinline!q(q)! and \lstinline!q(q(q))! because the full type signature
was declared for each of these expressions. Since the Scala compiler
did not print any error messages, we are assured that the types match
correctly.

\subsubsection{Example \label{subsec:Example-hof-curried}\ref{subsec:Example-hof-curried}}

Infer types in the code expression
\[
\left(f\rightarrow g\rightarrow g(f)\right)\left(f\rightarrow g\rightarrow g(f)\right)\left(f\rightarrow f(10)\right)
\]
and simplify the code through symbolic calculations.

\subparagraph{Solution}

The given expression is a curried function $f\rightarrow g\rightarrow g(f)$
applied to two curried arguments. The plan is to consider each of
these sub-expressions in turn, assigning types for them using type
parameters, and then to figure out how to set the type parameters
so that all types match.

Begin by renaming the shadowed variables ($f$ and $g$) to remove
shadowing:
\begin{equation}
\left(f\rightarrow g\rightarrow g(f)\right)\left(x\rightarrow y\rightarrow y(x)\right)\left(h\rightarrow h(10)\right)\quad.\label{eq:example-hof-curried-function-solved1}
\end{equation}
 As we have seen in Example~\ref{subsec:Example-hof-derive-types-5},
the sub-expression $f\rightarrow g\rightarrow g(f)$ is typed as $f^{:A}\rightarrow g^{:A\rightarrow B}\rightarrow g(f)$,
where $A$ and $B$ are some type parameters. The sub-expression $x\rightarrow y\rightarrow y(x)$
is the same function as $f\rightarrow g\rightarrow g(f)$ but with
possibly different type parameters, say, $x^{:C}\rightarrow y^{:C\rightarrow D}\rightarrow y(x)$.
The types $A$, $B$, $C$, $D$ are so far unknown.

Finally, the variable $h$ in the sub-expression $h\rightarrow h(10)$
must have type $\text{Int}\rightarrow E$, where $E$ is another type
parameter. So, the sub-expression $h\rightarrow h(10)$ is a function
of type $\left(\text{Int}\rightarrow E\right)\rightarrow E$.

The types must match in the entire expression~(\ref{eq:example-hof-curried-function-solved1}):
\begin{equation}
(f^{:A}\rightarrow g^{:A\rightarrow B}\rightarrow g(f))(x^{:C}\rightarrow y^{:C\rightarrow D}\rightarrow y(x))(h^{:\text{Int}\rightarrow E}\rightarrow h(10)\quad.\label{eq:example-hof-curried-function-solved2}
\end{equation}
It follows that $f$ must have the same type as $x\rightarrow y\rightarrow y(x)$,
while $g$ must have the same type as $h\rightarrow h(10)$. The type
of $g$, which we know as $A\rightarrow B$, will match the type of
$h\rightarrow h(10)$, which we know as $\left(\text{Int}\rightarrow E\right)\rightarrow E$,
only if $A=\left(\text{Int}\rightarrow E\right)$ and $B=E$. It follows
that $f$ has type $\text{Int}\rightarrow E$. At the same time, the
type of $f$ must match the type of $x\rightarrow y\rightarrow y(x)$,
which is $C\rightarrow(C\rightarrow D)\rightarrow D$. This can work
only if $C=\text{Int}$ and $E=(C\rightarrow D)\rightarrow D=(\text{Int}\rightarrow D)\rightarrow D$.

In this way, we have found all the relationships between the type
parameters $A$, $B$, $C$, $D$, $E$ in Eq.~(\ref{eq:example-hof-curried-function-solved2}).
The type $D$ remains arbitrary, while the type parameters $A$, $B$,
$C$, $E$ are expressed as
\begin{align}
A & =\text{Int}\rightarrow\left(\text{Int}\rightarrow D\right)\rightarrow D\quad,\label{eq:example-hof-curried-solved3}\\
B & =E=\left(\text{Int}\rightarrow D\right)\rightarrow D\quad,\label{eq:example-hof-curried-solved4}\\
C & =\text{Int}\quad.\nonumber 
\end{align}
The entire expression in Eq.~(\ref{eq:example-hof-curried-function-solved2})
is a saturated application of a curried function, and thus has the
same type as the \textsf{``}final\textsf{''} result expression $g(f)$, which has
type $B$. So, the entire expression in Eq.~(\ref{eq:example-hof-curried-function-solved2})
has type $B=\left(\text{Int}\rightarrow D\right)\rightarrow D$.

Having established that types match, we can now omit the type annotations
and rewrite the code:
\begin{align*}
 & (f\rightarrow g\rightarrow\gunderline g(\gunderline f))\left(x\rightarrow y\rightarrow y(x)\right)\left(h\rightarrow h(10)\right)\\
{\color{greenunder}\text{substitute }f=x\rightarrow y\rightarrow y(x)\text{ and }g=h\rightarrow h(10):}\quad & =(h\rightarrow\gunderline h(10))\left(x\rightarrow y\rightarrow y(x)\right)\\
{\color{greenunder}\text{substitute }h:}\quad & =(x\rightarrow y\rightarrow y(\gunderline x))(10)\\
{\color{greenunder}\text{substitute }x:}\quad & =y\rightarrow y(10)\quad.
\end{align*}
The type of this expression is $\left(\text{Int}\rightarrow D\right)\rightarrow D$
with a type parameter $D$. Since the argument $y$ is an arbitrary
function, we cannot simplify $y(10)$ or $y\rightarrow y(10)$ any
further. We conclude that the final simplified form of Eq.~(\ref{eq:example-hof-curried-function-solved1})
is $y^{:\text{Int}\rightarrow D}\rightarrow y(10)$.

To test this, we first define the function $f\rightarrow g\rightarrow g(f)$
as in Example~\ref{subsec:Example-hof-derive-types-5},
\begin{lstlisting}
def q[A, B]: A => (A => B) => B = { f => g => g(f) }
\end{lstlisting}
We also define the function $h\rightarrow h(10)$ with a general type
$\left(\text{Int}\rightarrow E\right)\rightarrow E$,
\begin{lstlisting}
def r[E]: (Int => E) => E = { h => h(10) }
\end{lstlisting}
To help Scala evaluate Eq.~(\ref{eq:example-hof-curried-function-solved2}),
we need to set the type parameters for the first \lstinline!q! function
as \lstinline!q[A, B]! where $A$ and $B$ are given by Eqs.~(\ref{eq:example-hof-curried-solved3})\textendash (\ref{eq:example-hof-curried-solved4}):
\begin{lstlisting}
scala> def s[D] = q[Int => (Int => D) => D, (Int => D) => D](q)(r)
s: [D]=> (Int => D) => D
\end{lstlisting}
To verify that the function $s^{D}$ indeed equals $y^{:\text{Int}\rightarrow D}\rightarrow y(10)$,
we apply $s^{D}$ to some functions of type $\text{Int}\rightarrow D$,
say, for $D=\text{Boolean}$ or $D=\text{Int}$:
\begin{lstlisting}
scala> s(_ > 0)  // Set D = Boolean and evaluate (10 > 0).
res6: Boolean = true

scala> s(_ + 20) // Set D = Int and evaluate (10 + 20).
res7: Int = 30
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-hof-composition}\ref{subsec:Example-hof-composition}}

Compute $\left(x\rightarrow y\rightarrow x(x(y))\right)\bef\left(p\rightarrow p(2)\right)\bef\left(z\rightarrow z+3\right)$
symbolically and infer types.

\subparagraph{Solution}

The forward composition $f\bef g$ substitutes the \emph{body} of
$f$ into the argument of $g$:
\begin{align*}
{\color{greenunder}\text{substitute }y=f(x):}\quad & \left(x\rightarrow f(x)\right)\bef(y\rightarrow\gunderline{g(y)})=\left(x\rightarrow g(f(x))\right)\quad.
\end{align*}
This allows us to compute the forward compositions left to right:
\begin{align*}
 & \left(x\rightarrow y\rightarrow x(x(y))\right)\bef(p\rightarrow p(2))=x\rightarrow(y\rightarrow x(x(y)))(2)=x\rightarrow x(x(2))\quad.\\
 & \left(x\rightarrow x(x(2))\right)\bef\left(z\rightarrow z+3\right)=x\rightarrow x(x(2))+3\quad.
\end{align*}
Computing the pairwise combinations in another order, we get:
\begin{align*}
 & \left(p\rightarrow p(2)\right)\bef\left(z\rightarrow z+3\right)=p\rightarrow p(2)+3\quad.\\
 & \left(x\rightarrow y\rightarrow x(x(y))\right)\bef\left(p\rightarrow p(2)+3\right)=x\rightarrow\left(y\rightarrow x(x(y))\right)(2)+3=x\rightarrow x(x(2))+3\quad.
\end{align*}
Types are inferred as $\left(x\rightarrow y\rightarrow x(x(y))\right)^{:(\text{Int}\rightarrow\text{Int})\rightarrow(\text{Int}\rightarrow\text{Int})}\bef\left(p\rightarrow p(2)\right)^{:(\text{Int}\rightarrow\text{Int})\rightarrow\text{Int}}\bef\left(z\rightarrow z+3\right)^{:\text{Int}\rightarrow\text{Int}}$.

\subsection{Exercises\index{exercises}}

\subsubsection{Exercise \label{subsec:Exercise-hof-simple-7}\ref{subsec:Exercise-hof-simple-7}}

Revise the function from Exercise~\ref{subsec:ch1-transf-Exercise-4},
implementing it as a curried function and replacing the hard-coded
number $100$ by a \emph{curried} first argument. The type signature
should become \texttt{}\lstinline!Int => List[List[Int]] => List[List[Int]]!\texttt{.}

\subsubsection{Exercise \label{subsec:Exercise-hof-simple-8}\ref{subsec:Exercise-hof-simple-8}}

Implement the function \lstinline!converge! from Example~\ref{subsec:Example-hof-simple-1}
as a curried function with an additional argument to set the maximum
number of iterations, returning \lstinline!Option[Double]! as the
final result type. The new version of \lstinline!converge! should
return \lstinline!None! if the convergence condition is not satisfied
after the given maximum number of iterations. The type signature and
an example test:
\begin{lstlisting}
@tailrec def convergeN[X](cond: X => Boolean)(x0: X)(maxIter: Int)(f: X => X): Option[X] = ???

scala> convergeN[Int](_ < 0)(0)(10)(_ + 1) // This does not converge.
res0: Option[Int] = None

scala> convergeN[Double]{ x => math.abs(x * x - 25) < 1e-8 }(1.0)(10) { x => 0.5 * (x + 25 / x ) }
res1: Option[Double] = Some(5.000000000053722)
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-hof-simple-7-1}\ref{subsec:Exercise-hof-simple-7-1}}

Implement a fully parametric, information-preserving, curried function
that recovers an error using a given function argument. The type signature
and an example test:
\begin{lstlisting}
def recover[E, A]: Option[Either[E, A]] => (E => A) => Option[A] = ???

scala> recover(Some(Left("error"))) { _ => 123 }
res0: Option[Int] = Some(123)
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-hof-simple-1}\ref{subsec:Exercise-hof-simple-1}}

For \lstinline!id! and \lstinline!const! as defined above, what
are the types of \lstinline!id(id)!, \lstinline!id(id)(id)!, \lstinline!id(id(id))!,
\lstinline!id(const)!, and \lstinline!const(const)!? Simplify these
code expressions by symbolic calculations.

\subsubsection{Exercise \label{subsec:Exercise-hof-simple-3}\ref{subsec:Exercise-hof-simple-3}}

For the function \lstinline!twice! from Example~\ref{subsec:Example-hof-derive-types-2},
infer the most general type for the function \lstinline!twice(twice(twice)))!.
What does that function do? Test your answer on an example.

\subsubsection{Exercise \label{subsec:Exercise-hof-simple-4}\ref{subsec:Exercise-hof-simple-4}}

Define a function \lstinline!thrice! similarly to \lstinline!twice!
except it should apply a given function $3$ times. What does the
function \lstinline!thrice(thrice(thrice)))! do?

\subsubsection{Exercise \label{subsec:Exercise-hof-simple-5}\ref{subsec:Exercise-hof-simple-5}}

Define a function \lstinline!ence! similarly to \lstinline!twice!
except it should apply a given function $n$ times, where $n$ is
an additional curried argument.

\subsubsection{Exercise \label{subsec:Exercise-hof-simple-6}\ref{subsec:Exercise-hof-simple-6}}

Define a fully parametric function \lstinline!flip(f)! that swaps
arguments for any given function \lstinline!f! having two arguments.
To test: 

\begin{lstlisting}
def f(x: Int, y: Int) = x - y    // Expect f(10, 2) == 8.
val g = flip(f)                  // Now expect g(2, 10) == 8.

scala> assert( f (10, 2) == 8 && g(2, 10) == 8 )
\end{lstlisting}


\subsubsection{Exercise \label{subsec:Exercise-hof-simple-8-1}\ref{subsec:Exercise-hof-simple-8-1}}

Write a function \lstinline!curry2! converting an uncurried function
of type \texttt{}\lstinline!(Int, Int) => Int! into an equivalent
curried function of type \texttt{}\lstinline!Int => Int => Int!.

\subsubsection{Exercise \label{subsec:Exercise-hof-curried-1}\ref{subsec:Exercise-hof-curried-1}}

Apply the function $\left(x\rightarrow\_\rightarrow x\right)$ to
the value $\left(z\rightarrow z(q)\right)$ where $q^{:Q}$ is a given
value of type $Q$. Infer types in these expressions.

\subsubsection{Exercise \label{subsec:Exercise-hof-curried-3}\ref{subsec:Exercise-hof-curried-3}}

Infer types in the following expressions and test in Scala:

\textbf{(a)} $p\rightarrow q\rightarrow p(t\rightarrow t(q))\quad.\quad\quad$
\textbf{(b)} $p\rightarrow q\rightarrow q(x\rightarrow x(p(q)))\quad.$

\subsubsection{Exercise \label{subsec:Exercise-hof-curried-4}\ref{subsec:Exercise-hof-curried-4}}

Show that the following expressions cannot be well-typed:

\textbf{(a)} $p\rightarrow p(q\rightarrow q(p))\quad.\quad\quad$\textbf{
(b)} $p\rightarrow q\rightarrow q(x\rightarrow p(q(x)))\quad.$

\subsubsection{Exercise \label{subsec:Exercise-hof-curried-2}\ref{subsec:Exercise-hof-curried-2}}

Infer types and simplify the following code expressions by symbolic
calculations:

\textbf{(a)} $q\rightarrow\left(x\rightarrow y\rightarrow z\rightarrow x(z)(y(z))\right)\left(a\rightarrow a\right)\left(b\rightarrow b(q)\right)\quad.$

\textbf{(b)} $\left(f\rightarrow g\rightarrow h\rightarrow f(g(h))\right)(x\rightarrow x)\quad.$

\textbf{(c)} $\left(x\rightarrow y\rightarrow x(y)\right)\left(x\rightarrow y\rightarrow x\right)\quad.$

\textbf{(d)} $\left(x\rightarrow y\rightarrow x(y)\right)\left(x\rightarrow y\rightarrow y\right)\quad.$

\textbf{(e)} $x\rightarrow\left(f\rightarrow y\rightarrow f(y)(x)\right)\left(z\rightarrow\_\rightarrow z\right)\quad.$

\textbf{(f)} $z\rightarrow\left(x\rightarrow y\rightarrow x\right)\left(x\rightarrow x(z)\right)(y\rightarrow y(z))\quad.$

\subsubsection{Exercise \label{subsec:Exercise-hof-composition}\ref{subsec:Exercise-hof-composition}}

Infer types and simplify the following code expressions by symbolic
calculations:

\textbf{(a)} $\left(z\rightarrow z+1\right)\bef\left(x\rightarrow y\rightarrow x/y\right)\bef\left(p\rightarrow p(2)\right)\quad.$

\textbf{(b)} $\left(p\rightarrow q\rightarrow p+q+1\right)\bef\left(f\rightarrow f\bef f\right)\bef(x\rightarrow x(1))\quad.$

\subsubsection{Exercise \label{subsec:Exercise-hof-composition-1}\ref{subsec:Exercise-hof-composition-1}{*}}

In the following statements, the types $A$ and $B$ are fixed, and
functions are \emph{not} assumed to be fully parametric in $A$ or
$B$.

\textbf{(a)} Given a function $h^{:A\rightarrow B}$ that satisfies
the law $f^{:A\rightarrow A}\bef h^{:A\rightarrow B}=h^{:A\rightarrow B}$
for any $f^{:A\rightarrow A}$, prove that the function $h$ must
ignore its argument and return a fixed value of type $B$.

\textbf{(b)} We are given two functions $g^{:A\rightarrow A}$ and
$h^{:B\rightarrow B}$. We know only that $g$ and $h$ satisfy the
law $f^{:A\rightarrow B}\bef h^{:B\rightarrow B}=g^{:A\rightarrow A}\bef f^{:A\rightarrow B}$
for any function $f^{:A\rightarrow B}$. Prove that both $g$ and
$h$ must be equal to identity functions of suitable types: $g^{:A\rightarrow A}=\text{id}^{A}$
and $h^{:B\rightarrow B}=\text{id}^{B}$.

Hint: choose $f$ to be a suitable \emph{constant} function and substitute
$f$ into the given laws.

\section{Further developments}

\subsection{Higher-order functions}

The \textbf{order\index{order of a function}} of a function is the
number of function arrows (\lstinline!=>!) contained in the type
signature of that function. If a function\textsf{'}s type signature contains
more than one arrow, the function is called a \textbf{\index{higher-order function}higher-order}
function. Higher-order functions take functions as arguments and/or
return functions.

The methods \lstinline!andThen!, \lstinline!compose!, \lstinline!curried!,
and \lstinline!uncurried! are examples of higher-order functions
that take other functions as arguments \emph{and} return new functions.

The following examples illustrate the concept of a function\textsf{'}s order.
Consider the code
\begin{lstlisting}
def f1(x: Int): Int = x + 10
\end{lstlisting}
The function \texttt{}\lstinline!f1! has type signature \texttt{}\lstinline!Int => Int!
and order $1$, so it is \emph{not} a higher-order function.
\begin{lstlisting}
def f2(x: Int): Int => Int = (z => z + x)
\end{lstlisting}
The function \texttt{}\lstinline!f2! has type signature \texttt{}\lstinline!Int => Int => Int!
and is a higher-order function of order $2$. 
\begin{lstlisting}
def f3(g: Int => Int): Int = g(123)
\end{lstlisting}
The function \texttt{}\lstinline!f3! has type signature \texttt{}\lstinline!(Int => Int) => Int!
and is a higher-order function of order $2$.

Note that \texttt{}\lstinline!f2! is a higher-order function only
because its return value is of a function type. An equivalent computation
can be performed by an uncurried function that is not higher-order:
\begin{lstlisting}
scala> def f2u(x: Int, z: Int): Int = z + x    // Type signature (Int, Int) => Int
\end{lstlisting}
Unlike \lstinline!f2!, the function \lstinline!f3! \emph{cannot}
be converted to a non-higher-order function because \lstinline!f3!
has an argument of a function type. Converting to an uncurried form
cannot eliminate such arguments.

\subsection{Name shadowing and the scope of bound variables}

Bound variables are introduced in nameless functions whenever an argument
is defined. For example, in the nameless function $x\rightarrow y\rightarrow x+y$,
the bound variables are the curried arguments $x$ and $y$. The variable
$y$ is only defined within the scope $\left(y\rightarrow x+y\right)$
of the inner function; the variable $x$ is defined within the entire
scope of $x\rightarrow y\rightarrow x+y$.

Another way of introducing bound variables in Scala is to write a
\lstinline!val! or a \lstinline!def! within curly braces:
\begin{lstlisting}
val x = {
  val y = 10          // Bound variable `y`.
  y + y * y
}     // Same as `val x = 10 + 10 * 10`.
\end{lstlisting}

A bound variable is invisible outside the scope that defines it. So,
it is easy to rename a bound variable: no outside code could possibly
use it and depend on its value.

However, outside code may define a variable that (by chance) has the
same name as a bound variable inside the scope. Consider this example
from calculus: In the integral
\[
f(x)=\int_{0}^{x}\frac{dx}{1+x}\quad,
\]
\emph{two} bound variables named $x$ are defined in two scopes: one
in the scope of $f$, another in the scope of the nameless function
$x\rightarrow\frac{1}{1+x}$. The convention in mathematics is to
treat these two $x$\textsf{'}s as two \emph{completely} \emph{different} variables
that just happen to have the same name. In sub-expressions where both
of these bound variables are visible, priority is given to the bound
variable defined in the smaller inner scope. The outer definition
of $x$ is then \textbf{shadowed}\index{shadowed name} (hidden) by
the inner definition of $x$. For this reason, evaluating $f(10)$
will give
\[
f(10)=\int_{0}^{10}\frac{dx}{1+x}=\log_{e}(11)\approx2.398\quad,
\]
rather than $\int_{0}^{10}\frac{dx}{1+10}=\frac{10}{11}$. The outer
definition $x=10$ is shadowed within the expression $\frac{1}{1+x}$
by the definition of $x$ in the smaller local scope of $x\rightarrow\frac{1}{1+x}$.

Since this is the standard mathematical convention, the same convention
is adopted in functional programming. A variable defined in a function
scope (i.e., a bound variable) will shadow any outside definitions
of a variable with the same name.

Name shadowing is not advisable in practical programming, because
it usually decreases the clarity of code and so invites errors. Consider
the nameless function
\[
x\rightarrow x\rightarrow x\quad,
\]
and let us decipher this confusing syntax. The symbol $\rightarrow$
groups to the right, so $x\rightarrow x\rightarrow x$ is the same
as $x\rightarrow\left(x\rightarrow x\right)$. It is a function that
takes $x$ and returns $x\rightarrow x$. Since the argument $x$
in $\left(x\rightarrow x\right)$ may be renamed to y without changing
the function, we can rewrite the code to
\[
x\rightarrow\left(y\rightarrow y\right)\quad.
\]
Having removed name shadowing, we can more easily understand this
code and reason about it. For instance, it becomes clear that this
function ignores its argument $x$ and always returns the same value
(the identity function $y\rightarrow y$). So we can rewrite $\left(x\rightarrow x\rightarrow x\right)$
as $\left(\_\rightarrow y\rightarrow y\right)$, which is clearer.

\subsection{Operator syntax for function applications}

In mathematics, function applications are sometimes written without
parentheses, for instance $\cos x$ or $\sin z$. Formulas such as
$2\sin x\cos x$ imply parentheses as $2\cdot\sin\left(x\right)\cdot\cos\left(x\right)$.
Functions such as $\cos x$ are viewed as \textsf{``}operators\textsf{''} that are
applied to their arguments without parentheses, similar to the operators
of summation $\sum_{k}f(k)$ and differentiation $\frac{d}{dx}f(x)$.

Many programming languages (such as ML, OCaml, F\#, Haskell, Elm,
PureScript) have adopted this \textsf{``}operator syntax\index{operator syntax}\textsf{''},
making parentheses optional for function arguments so that \lstinline!f x!
means the same as \lstinline!f(x)!. Parentheses are still used where
necessary to avoid ambiguity or for readability.\footnote{The operator syntax has a long history in programming. It is used
in Unix shell commands, for example \lstinline!cp file1 file2!. In
LISP-like languages, function applications are enclosed in parentheses
but the arguments are space-separated, for example \lstinline!(f 10 20)!.
Operator syntax is also used in some programming languages such as
Tcl, Groovy, and Coffeescript.}

The conventions for nameless functions in the operator syntax become:
\begin{itemize}
\item Function expressions group to the right, so $x\rightarrow y\rightarrow z\rightarrow e$
means $x\rightarrow\left(y\rightarrow\left(z\rightarrow e\right)\right)$.
\item Function applications group to the left, so $f\,x\,y\,z$ means $\big((f\,x)\,y\big)\,z$.
\item Function applications group stronger than infix operations, so $f\,x+y$
means $(f\,x)+y$, just as in mathematics \textsf{``}$\cos x+y$\textsf{''} groups
\textsf{``}$\cos x$\textsf{''} stronger than the infix \textsf{``}$+$\textsf{''} operation.
\end{itemize}
Thus, $x\rightarrow y\rightarrow a\,b\,c+p\,q$ means $x\rightarrow\left(y\rightarrow\left(\left(a\,b\right)\,c\right)+(p\,q)\right)$.
When this notation becomes hard to read correctly, one needs to add
parentheses, e.g., writing $f(x\rightarrow g\,h)$ instead of $f\,x\rightarrow g\,h$.

This book will not use the \textsf{``}operator syntax\textsf{''} when reasoning about
code. Scala does not support the parentheses-free operator syntax;
parentheses are needed around each curried argument.

In programming language theory, curried functions are \textsf{``}simpler\textsf{''}
because they always have a \emph{single} argument (but may return
a function that will consume further arguments). From the point of
view of programming practice, curried functions are often harder to
read and to write.

In the operator syntax, a curried function \lstinline!f! is applied
to curried arguments as, e.g., \lstinline!f 20 4!. This departs further
from the mathematical tradition and requires some getting used to.
If the two arguments are more complicated than just $20$ and $4$,
the resulting expression may become harder to read, compared with
the syntax where commas are used to separate the arguments. (Consider,
for instance, the expression \lstinline!f (g 10) (h 20) + 30!.) To
improve readability of code, programmers may prefer to define names
for complicated expressions and then use those names as curried arguments.

In Scala, the choice of whether to use curried or uncurried function
signatures is largely a matter of syntactic convenience. Most Scala
code tends to be written with uncurried functions, while curried functions
are used when they produce more easily readable code.

One of the syntactic features for curried functions in Scala is the
ability to specify a curried argument using the curly brace syntax.
Compare the two definitions of the function \lstinline!summation!
described in Section~\ref{subsec:Nameless-functions-in-mathematical-notation}:
\begin{lstlisting}
def summation1(a: Int, b: Int, g: Int => Int): Int = (a to b).map(g).sum

def summation2(a: Int, b: Int)(g: Int => Int): Int = (a to b).map(g).sum
\end{lstlisting}
These functions are applied to arguments like this:

\begin{wrapfigure}{l}{0.48\columnwidth}%
\vspace{-0.5\baselineskip}
\begin{lstlisting}
scala> summation1(1, 10, { x => x*x*x + 2*x })
res0: Int = 3135

scala> summation2(1, 10) { x => x*x*x + 2*x }
res1: Int = 3135
\end{lstlisting}
\vspace{-0.75\baselineskip}
\end{wrapfigure}%

\noindent The code that calls \lstinline!summation2! is easier to
read because the curried argument is syntactically separated from
the rest of the code by curly braces. This is especially useful when
the curried argument is itself a function with a complicated body,
since Scala\textsf{'}s curly braces syntax allows function bodies to contain
local definitions (\lstinline!val! or \lstinline!def!) of new bound
variables.

Another feature of Scala is the \textsf{``}dotless\textsf{''} method syntax: for example,
\lstinline!xs map f! is equivalent to \lstinline!xs.map(f)! and
\lstinline!f andThen g! is equivalent to \lstinline!f.andThen(g)!.
The \textsf{``}dotless\textsf{''} syntax is available only for infix methods, such
as \lstinline!map!, defined on specific types such as \lstinline!Seq!.
In Scala 3, the \textsf{``}dotless\textsf{''} syntax will only work for methods having
a special \lstinline!@infix! annotation. Do not confuse Scala\textsf{'}s \textsf{``}dotless\textsf{''}
method syntax with the operator syntax used in Haskell and other languages.

\subsection{Deriving a function\textsf{'}s code from its type\label{subsec:Deriving-a-function-s-code}}

We have seen how the procedure of type inference\index{type inference}
derives the type signature from a function\textsf{'}s code. A well-known algorithm
for type inference is the Damas-Hindley-Milner algorithm,\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Hindley\%E2\%80\%93Milner_type_system}{https://en.wikipedia.org/wiki/Hindley\%E2\%80\%93Milner\_type\_system}}}
with a Scala implementation available.\footnote{\texttt{\href{http://dysphoria.net/2009/06/28/hindley-milner-type-inference-in-scala/}{http://dysphoria.net/2009/06/28/hindley-milner-type-inference-in-scala/}}}

It is remarkable that one can sometimes perform \textsf{``}\index{code inference}code
inference\textsf{''}: derive a function\textsf{'}s \emph{code} from the function\textsf{'}s
type signature. We will now look at some examples of this.

Consider a fully parametric function that performs partial applications\index{partial application}
for arbitrary other functions. A possible type signature is
\begin{lstlisting}
def pa[A, B, C](x: A)(f: (A, B) => C): B => C = ???
\end{lstlisting}
The function \lstinline!pa! substitutes a fixed argument value \lstinline!x:A!
into another given function \lstinline!f!. 

How can we implement \lstinline!pa!? Since \lstinline!pa(x)(f)!
must return a function of type \lstinline!B => C!, we have no choice
other than to begin writing a nameless function in the code,
\begin{lstlisting}
def pa[A, B, C](x: A)(f: (A, B) => C): B => C = { y: B =>
  ??? // Need to compute a value of type C in this scope.
}
\end{lstlisting}
In the inner scope, we need to compute a value of type \lstinline!C!,
and we have values \lstinline!x:A!, \lstinline!y:B!, and \lstinline!f:(A, B)=>C!.
How can we compute a value of type \lstinline!C!? If we knew that
\lstinline!C = Int! when \lstinline!pa(x)(f)! is applied, we could
have simply selected a fixed integer value, say, \lstinline!1!, as
the value of type \lstinline!C!. If we knew that \lstinline!C = String!,
we could have selected a fixed string, say, \lstinline!"hello"!,
as the value of type \lstinline!C!. But a fully parametric function
cannot use any knowledge of the types of its actual arguments.

So, a fully parametric function cannot produce a value of an arbitrary
type \lstinline!C! from scratch. The only way of producing a value
of type \lstinline!C! is by applying the function \lstinline!f!
to arguments of types \lstinline!A! and \lstinline!B!. Since the
types \lstinline!A! and \lstinline!B! are arbitrary, we cannot obtain
any values of these types other than \lstinline!x:A! and \lstinline!y:B!.
So, the only way of getting a value of type \lstinline!C! is to compute
\lstinline!f(x, y)!. Thus, the body of \lstinline!pa! must be
\begin{lstlisting}
def pa[A, B, C](x: A)(f: (A, B) => C): B => C = { y => f(x, y) }
\end{lstlisting}
In this way, we have \emph{unambiguously} derived the body of this
function from its type signature, by assuming that the function must
be fully parametric.

Another example is the operation of forward composition $f\bef g$
viewed as a fully parametric function with type signature
\begin{lstlisting}
def before[A, B, C](f: A => B, g: B => C): A => C = ???
\end{lstlisting}
To implement \lstinline!before!, we need to create a nameless function
of type \lstinline!A => C!,
\begin{lstlisting}
def before[A, B, C](f: A => B, g: B => C): A => C = { x: A =>
  ??? // Need to compute a value of type C in this scope.
}
\end{lstlisting}
In the inner scope, we need to compute a value of type $C$ from the
values $x^{:A}$, $f^{:A\rightarrow B}$, and $g^{:B\rightarrow C}$.
Since the type $C$ is arbitrary, the only way of obtaining a value
of type $C$ is by applying $g$ to an argument of type $B$. In turn,
the only way of obtaining a value of type $B$ is to apply $f$ to
an argument of type $A$. Finally, we have only one value of type
$A$, namely $x^{:A}$. So, the only way of obtaining the required
result is to compute $g(f(x))$.

We have unambiguously inferred the body of the function from its type
signature:
\begin{lstlisting}
def before[A, B, C](f: A => B, g: B => C): A => C = { x => g(f(x)) }
\end{lstlisting}

In Chapter~\ref{chap:5-Curry-Howard} and in Appendix~\ref{app:CH-correspondence-LJT-algorithm},
we will see how code can be derived from type signatures for a wide
range of fully parametric functions.
